Given an array A having positive and negative unique integers and a number k, find all the pairs in the array which sums = k.

Here we have an array of positive and negative integers and a number k. We need to find all the pairs in the array which sums to k. As the array is of unique integers so we do not have any duplicate values. Consider the following example, where we have an input array as:

int [ ] arr = {1,3,-5,9,4,5,6,7,11,15,-1,8} and k = 10.

So the output pairs which sums to k (10) in the above array are :

Pair Found : 1 and 9
Pair Found : 4 and 6
Pair Found : 3 and 7
Pair Found : -5 and 15
Pair Found : 11 and -1

Algorithm :
1. We will use a HashMap to store all the pair.

Map to store the Pairs
Key Value
( k - a[i] ) a[i] 
2. For each element in the array 
    2.1  Find the difference between k and a[i] = ( k - a[i] ).
    2.2  Check if map has an entry with key a[i]. If present the it is a pair. Print the pair.
    2.3  Put the value in map. As map.put((k - arr[i]),a[i])

And at the end of the iteration step 2.2 will print all the pairs.

Now check this algorithm with some real life values to have a better understanding. Consider we have values in array as {1,2,9} and we are searching pairs for k = 10.

Iterate over the array.

    a. Here a[0] = 1
       int diff = ( k - a[0] ) = ( 10 - 1 ) = 9
       check if value is present in map with key a[0] = 1
       No then put in map (diff,a[i])) = map(9,1)
       
    b. Here a[1] = 2
       int diff = ( k - a[1] ) = ( 10 - 2 ) = 8
       check if value is present in map with key a[1] = 2
       No then put in map (diff,a[i])) = map(8,2)
       
    c. Here a[2] = 9
       int diff = ( k - a[1] ) = ( 10 - 9 ) = 1
       check if value is present in map with key a[2] = 9
       Present , then print the pair { a[2],value with key a[2] or diff } = (9,1)

Now the implementation is

package com.tuturself.algo;

import java.util.HashMap;
import java.util.Map;

public class FindPairSumsK {

  public static void findAndPrintPairs(int[] arr, int k) throws Exception {
    if (arr == null || arr.length < 2) {
        throw new Exception("Invalid input");
    }

    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < arr.length; i++) {
        int diff = (k - arr[i]);
        if (map.get(arr[i]) != null) {
            System.out.println("Pair Found : " + diff + " and " + arr[i]);
        } else {
            map.put(diff, arr[i]);
        }

    }
  }

  public static void main(String[] args) throws Exception {
    int[] arr = {1, 3, -5, 9, 4, 5, 6, 7, 11, 15, -1, 8};
    findAndPrintPairs(arr, 10);
  }
}

Output :

Pair Found : 1 and 9
Pair Found : 4 and 6
Pair Found : 3 and 7
Pair Found : -5 and 15
Pair Found : 11 and -1


 

core java 12 Algorithm 12

FOLLOW US ON LinkedIn



Explore Tutu'rself