2

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.

Shadow
  • 29
  • 5

3 Answers3

3

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)
Azher Aleem
  • 518
  • 4
  • 14
1

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]);
}
Eran
  • 374,785
  • 51
  • 663
  • 734
  • but the hashset contains method itself having O(N) complexity for each element – Shadow Jul 14 '20 at 06:08
  • 2
    @Shadow No, `HashSet`'s `contains()` has expected O(1) complexity. – Eran Jul 14 '20 at 06:08
  • No, it is O(1). – Unmitigated Jul 14 '20 at 06:08
  • Thanks for the answer, but this will print a number twice right? – Shadow Jul 14 '20 at 06:12
  • 17,4 1,20 12,9 4,17 20,1 9,12 I hope the answer will print like this – Shadow Jul 14 '20 at 06:13
  • 1
    @Shadow no. When you encounter the first number of a pair, the second number of the pair is not yet in the Set, so the pair is not printed until you encounter the second number. – Eran Jul 14 '20 at 06:13
  • One answer is output for `{20, 20, 1}`. But two answers for `{20, 1, 20}`. –  Jul 14 '20 at 07:22
  • @saka1029 in case of duplicates, you have to specify what's the desired behavior. If you want to always eliminate duplicates, it's possible to output the pair only if `arr[i]` is not yet in the Set. If you want to output duplicates, you can use a Map instead of Set and count the occurrences of each number. – Eran Jul 14 '20 at 08:59
1

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.

Daniel
  • 6,573
  • 5
  • 23
  • 62