Make delicious recipes!

Find all pairs with a given sum


Problem: Given an unsorted array, find all pairs whose sum is a given number K


  1. Solution 1: Use a hash-map to store all numbers.
    When storing a number in the map, lookup N-k.
    If N-k exists in the map, sum is found, else move to next number.


  2. Solution 2: Sort the array and search with two indexes set to start and end of the array.
    int start = 0;
    int end = arr.length;
    
    while (start <= end)
    {
        int sum = arr[start] + arr[end];
        if (sum == K)
        {
            System.out.println ("Found sum for " + arr[start] + " and " + arr[end]);
            start++;
            end--;
        }
        else if (sum < K)
        {
            start++;
        }
        else
        {
            end--;
        }
    }
    


Find all triplets with a given sum


A corollary of the above question is to find all triplets with a given sum.

Since the best case for finding pairs was O(n log n) for sorting and then O(n) for finding pairs, it
follows that the order for triplets would be greater than or equal to that.

Taking liberty due to this, let us first sort the array.

Now for each number in the sorted array, we can find a pair whose sum is S-arr[k]

Since finding pairs for a given sum is O(n) in sorted array, the whole operation becomes O(n log n ) + O(n2)

Which is equal to O(n2)



Now find all quadruples with a given sum


  1. Find sum of all pairs using two loops - O(n2) to get k (i.e. n(n-1)/2) numbers
  2. Sort these k numbers - O (k log k) = O(n2 log n2) = O(n2 log n)
  3. Find pairs in these sorted 'k' numbers whose sum is the given sum and which do not have any common element from the original array.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal