Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Determine whether or not there exist two elements in Set S whose sum is exactly x - correct solution?

Taken from Introduction to Algorithms

Describe a Θ(n lg n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

This is my best solution implemented in Java so far:

    public static boolean test(int[] a, int val) {
    mergeSort(a);

    for (int i = 0; i < a.length - 1; ++i) {
        int diff = (val >= a[i]) ? val - a[i] : a[i] - val;

        if (Arrays.binarySearch(a, i, a.length, diff) >= 0) {
            return true;
        }
    }

    return false;
}

Now my 1st question is: Is this a correct solution? From my understanding, mergeSort should perform the sort in O(n lg n), the loop should take O(n lg n) (n for the iteration multiplied by O(lg n) for the binary search, resulting in O(2n lg n), so it should be correct.

My 2nd question is: Are there any better solutions? Is sorting the array essential?

like image 437
helpermethod Avatar asked Jan 31 '10 14:01

helpermethod


People also ask

How do you find all pairs of elements in an array whose sum is equal to given number?

Follow the steps below to solve the given problem: Initialize the count variable with 0 which stores the result. Iterate arr and if the sum of ith and jth [i + 1…..n – 1] element is equal to sum i.e. arr[i] + arr[j] == sum, then increment the count variable. Return the count.

How do you find all pairs of an integer array whose sum is equal to a given number in C?

C program to find a pair of number whose sum is K using hash table. Sort inputArray using any O(nLogn) time sorting algorithm. Initialize leftIndex and rightIndex to 0 and N-1 respectively. If inputArray[leftIndex] + inputArray[rightIndex] is equal to K, then we found a pair.


3 Answers

Your solution seems fine. Yes you need to sort because its a pre requisite for binary search. You can make a slight modification to your logic as follows:

public static boolean test(int[] a, int val)  {     Arrays.sort(a);      int i = 0;            // index of first element.     int j = a.length - 1; // index of last element.       while(i<j)     {         // check if the sum of elements at index i and j equals val, if yes we are done.         if(a[i]+a[j] == val)             return true;         // else if sum if more than val, decrease the sum.         else if(a[i]+a[j] > val)             j--;         // else if sum is less than val, increase the sum.         else             i++;     }     // failed to find any such pair..return false.      return false; } 
like image 80
codaddict Avatar answered Sep 19 '22 19:09

codaddict


There's another very fast solution: Imagine you have to solve this problem in Java for about 1 billions integers. You know that in Java integers go from -2**31+1 to +2**31.

Create an array with 2**32 billion bit (500 MB, trivial to do on today's hardware).

Iterate over your set: if you have an integer, set corresponding bit to 1.

O(n) so far.

Iterate again over your set: for each value, check if you have a bit set at "current val - x".

If you have one, you return true.

Granted, it needs 500 MB of memory.

But this shall run around any other O(n log n) solution if you have, say, to solve that problem with 1 billion integers.

O(n).

like image 37
SyntaxT3rr0r Avatar answered Sep 19 '22 19:09

SyntaxT3rr0r


  1. This is correct; your algorithm will run in O(n lg n) time.

  2. There is a better solution: your logic for calculating diff is incorrect. Regardless of whether a[i] is greater than or less than val, you still need diff to be val - a[i].

like image 26
danben Avatar answered Sep 22 '22 19:09

danben