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

Question

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?

Answer 1

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; } 

Answer 2

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).

Answer 3

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].