Let A[1..n] be an array of distinct positive integers, and let t be a positive integer.(a) Assuming that A is sorted, show that in O(n) time it can be decided if A contains two distinct elements x and y such that x + y = t.

(b) Use part (a) to show that the following problem, referred to as the 3-Sum problem, can be solved in O(n2) time: 3-Sum Given an array A[1..n] of distinct positive integers that is not (necessarily) sorted, and a positive integer t, de- termine whether or not there are three distinct elements x, y, z in A such that x + y + z = t.

a) 2-SUM PROBLEM

(Use Hashing)

This method works in O(n) time.

1) Initialize an empty hash table s.

2) Do following for each element A[i] in A[]

  (a)    If s[t - A[i]] is set then print the pair (A[i], t - A[i])

  (b)    Insert A[i] into s.

b)

The complexity can be reduced to O(n^2) by sorting the array first, and then using method 1 of this post in a loop.

1) Sort the input array.

2) Fix the first element as A[i] where i is from 0 to array size – 2. After fixing the first element of triplet, find the other two elements using method 1 of this post.

Below is the psudocode

bool find3Numbers(int A[], int arr_size, int sum)

{

   int l, r;

   /* Sort the elements */

   sort(A, A + arr_size);

   /* Now fix the first element one by one and find the

      other two elements */

   for (int i = 0; i < arr_size - 2; i++) {

       // To find the other two elements, start two index

       // variables from two corners of the array and move

       // them toward each other

       l = i + 1; // index of the first element in the

       // remaining elements

       r = arr_size - 1; // index of the last element

       while (l < r) {

           if (A[i] + A[l] + A[r] == sum) {

               printf("Triplet is %d, %d, %d", A[i],

                      A[l], A[r]);

               return true;

           }

           else if (A[i] + A[l] + A[r] < sum)

               l++;

           else // A[i] + A[l] + A[r] > sum

               r--;

       }

   }

   // If we reach here, then no triplet was found

   return false;

}