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 analysis is correct, and yes you must sort the array or else binary search does not work.

Answer 2

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 3

I do think I have spotted a minor bug in your implementation, but testing should uncover that one quickly.

The approach looks valid, and will reach the desired performance. You might simplify it by replacing the iterative binary search with a scan through the array, in effect replacing the binary search by a linear search that resumes where the previous linear search left off:

int j = a.length - 1;
for (int i = 0; i < a.length; i++) {
    while (a[i] + a[j] > val) {
        j--;
    }
    if (a[i] + a[j] == val) {
        // heureka!
    }
}

This step is O(n). (Proving that is left as an exercise for you.) Of course, the entire algorithm still takes O(n log n) for the merge sort.

Answer 4

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

Answer 5

Here's an O(n) solution using a hash-set:

  public static boolean test(int[] a, int val) {
      Set<Integer> set = new HashSet<Integer>();

      // Look for val/2 in the array
      int c = 0;
      for(int n : a) {
        if(n*2 == val)
          ++c
      }
      if(c >= 2)
         return true; // Yes! - Found more than one

      // Now look pairs not including val/2
      set.addAll(Arrays.asList(a));
      for (int n : a) {
         if(n*2 == val)
            continue;
         if(set.contains(val - n))
            return true;
      }

      return false;
   }

Answer 6

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 7

A simple solution is, after sorting, move pointers down from both ends of the array, looking for pairs that sum to x. If the sum is too high, decrement the right pointer. If too low, increment the left one. If the pointers cross, the answer is no.