Let A[1..n] be an array of distinct positive integers, and let t be a positive i

Question

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.(please answer the B category)

Explanation / Answer

For part (b) we first sort the array. This takes O(nlogn) time.

Then for every element of A, we try to find the other 2 elements so that the sum of these 3 elements is equal to t. This takes O(n2) time. So, the total time is O(n2).

The following function in C++ performs this operation:-

bool sum(int A[],int n,int t)
{
sort(A,A+n); //sorting the array
for (int i=0;i<n-2;i++) //fixing the element A[i] as the first element
{
int l=i+1; //Taking element next to index i as the second element
int r =n-1; //Taking the last element of array as the third element
while(l<r) //performing following function till l<r
{
if(A[i]+A[l]+A[r]==t) //if we have got the 3 elements, then display them and return true
{
cout<<"The 3 numbers are"<<A[i]<<" "<<A[l]<<" "<<A[r];
return true;
}
  
/*if sum of these 3 elements is less than t, then incrementing l
because array is sorted and element next to l will be greater than A[l]*/
else if (A[i]+A[l]+A[r]<t)
l++;
  
/*if sum of these 3 elements is greater than t, then decrementing r
because array is sorted and element before r will be lesser than A[r]*/   
else
r--;
}
}
//if we have arrived here, it means that we have not got the elements, so we return false
return false;
}

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.