Couple sum in array

user_13926893 0
Viewed 227

I have an array of integer says [17, 1, 20, 4, 12, 9] I want to get all the couple whose sum is 21. for example in given array output should be like:

17,4
1,20
12,9

I could achieve the same using two loops. But the complexity goes N^2. Is there any efficient way to do this.

algorithm java
3 Answers

Here is a piece of solution using python 3.0+.

You can do it in O(N) by using key-pair value data structure i.e. a dictionary.

Approach:

  1. Loop once through the array and check if the result of value k subtracted from the current element i.e. (k-arr[i]) is present in the dictionary means that the sum of the resultant value k-arr[i] and current element arr[i] equal to k. Add these two to the dictionary.

  2. If k-arr[i] is not present in the dictionary then add the key arr[i] with value being k-arr[i].

  3. You may also add check for current element arr[i] being greater than k.

     def getPair(arr, k, dict):
     for i in range(len(arr)):
         if k - arr[i] in dict.keys():
             pass
             #print(arr[i], " ", (k-arr[i]))
         else:
             if k > arr[i]:
                 dict[arr[i]] = (k-arr[i])

 arr = [17, 1, 20, 4, 12, 9, 23]
 dict = {}
 getPair(arr, 21, dict)
 print("result: " , dict)
user_59687030

Use a HashSet.

For example, put all the elements in a HashSet (single loop, O(N)).

Then iterate over the elements again, and for each element i, check if the HashSet contains 21-i. That would also take O(N).

You can further optimize and do both steps in a single loop, but that won't change the asymptotic O(N) running time.

Set<Integer> set = new HashSet<>();
for (int i=0;i<arr.length;i++) {
    if (set.contains(21 - arr[i])) {
        System.out.println(arr[i] + ", " + (21 - arr[i]));
    }
    set.add (arr[i]);
}
user_12215710

Here's a piece of working code with your example, using HashSet:

import java.util.*;

public class Main{
    public static void main(String[] args) {
        int[] arr = new int[]{17, 1, 20, 4, 12, 9};
        HashSet<Integer> hash = new HashSet<Integer>(); 
        int sum = 21;
        
        for(int i = 0; i < arr.length; i++){
            hash.add(arr[i]);
        }
        
        for(int i = 0; i < arr.length; i++){
            if(hash.contains(sum - arr[i])){
                System.out.println(arr[i] + " and " + (sum - arr[i]));
                hash.remove(arr[i]);
            }
        }
    }
}

The complexity is O(n). The idea is to add all numbers of the array in the HashSet. Then, iterate through the array and check if, for each element arr[i], sum - arr[i] is in the HashSet. If it is, it means you have a matching pair, so you remove one of the elements of the pair to avoid repeating matches.

user_53488750
Related