.

Algorithms | Getting pairs which result in desired sum out of integer array

Problem

We have n integers in a int array. Print all the combinations whose sum is a particular number.
    Eg. -2, -4, -1 , 0, 1, 7 ,5, 8 ,2
    If those pairs are required whose sum is 6, then output should be
    -2, 8
    -1, 7
     1, 5

     > Use any programming language
     > It should have complexity <= N


Solution

As we need a solution with complexity less than or equal to N, there fore we can't use bruite-force. One solution is the keep the number and it's compliment in hashmap and search in hashmatp while iterating over those number.

If a match is found then we can print the numbers otherwise we can skip that.

We are using Java.

 public static void main(String[] args) {
  int a[] = { -7, 11, -3, -2, 0, 2, 13, 3, 6, -5 };
  int targetSum = 6;

  Map<integer integer=""> opMap = new HashMap<>();

  for (int i = 0; i < a.length; i++) {
   if (opMap.containsValue(a[i])) {
    System.out.println((targetSum - a[i]) + " , " + a[i]);
   }
   opMap.put(a[i], targetSum - a[i]);
  }

 }


No comments :

Post a Comment

Recent Posts