Question

3. 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, re- ferred to as the 3-Sum problem, can be solved in O(n2) time:

   1. 3-Sum

      Given an array A[1..n] of distinct positive integers, and a positive integer t, determine whether or not there are three distinct elements x, y, z in A such that x+y+z = t.

Answer 1

`Hey,

Note: Brother if you have any queries related the answer please do comment. I would be very happy to resolve all your queries.

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;

}

Kindly revert for any queries

Thanks.