Given n distinct integers, we want to know how many triples ( x , y , z ), where

Question

Given n distinct integers, we want to know how many triples (x, y, z), where x y z, sum to exactly zero. Note that the order of the triple does not matter, i.e., (x, y, z) is considered to be the same as (z, y, x).Example: There are 4 triples that sum to zero in the array:

[3 4 2 1 4 0 1]

i.e., the triples (3, 4, 1), (3, 2, 1), (4, 4, 0), (1, 0, 1).

Consider the following pseudocode, which, given an input of n distinct integers, counts the number of triples that sum exactly to zero:

3-Sum-to-0(A[1…n])
01 count = 0
02 for i = 1 to n
03   for j = i + 1 to n
04   for k = j + 1 to n
05   if A[i] + A[j] + A[k] == 0
06 count = count + 1
07 return count

1. Let T(n) be the number of times the array A is accessed (for values A[i], A[j], A[k]) as a function of input size n. Express T(n) as a summation (actually three nested summations). Find T(n), i.e., simplify the summation. Show all your work.

2. Write a divide-and-conquer algorithm with worst-case running time O(n2 lgn) that solves the problem.

a )Describe your algorithm in pseudocode.

b) Prove that your algorithm correctly solves the problem.

c) Analyze running time of your algorithm. For credit, you must analyze your pseudocode and explains how it achieves its O(n2 lgn) running time.

Explanation / Answer

2) Binary search is one of the partial application of divide and conquer.

In our question we are given a set of unsorted array .   

a)Algorithm:

Mergesort(a,i,j) // a is array, 'i' is 1st element, 'j' is last element

{

if(i=j) // if there is only 1 element return the value

return(a[i]);

else

{

mid = (i+j)/2; // find the mid value and divide the array into 2 parts

Mergesort(a,i,mid); // sort the first part

Mergesort(a,mid+1,j); //sort the secong part

merge(a,i,mid,mid+1,j); // combine both parts and return sorted array

return a;

}

}

Finding triplet algorithm

int count=0; //declare count globally so the value donot change for each time the loop runs

for (int i = 0; i < arr_size - 3; i++) //the first value is fixed and loop runs

    {

for(int j=1; j< arr_size - 2; j++) //the second value is fixed and loop runs

{

x= j+1; // consider from the 3rd element the values for binary search

y= arr_size-1; // initializing the last element of array

while(x<y) // binary search starts here and loop continues till it will find the value

{

mid =x+y/2; // find the mind values in the reamining set of elements

sum= a[i]+a[j]+a[mid]; // find the sum

if (sum == 0) // if value is equal to zero tripletfound and count increments

count= count +1;

else if(sum<0) //if value less than sum consider less values than mid value

y=mid+1;

else if(sum>0) //if value greater than sum consider higher value than mid

x=mid-1;

else return 0; //if no triplet found

}

}

}

b) In the above algorithm firstle the merge sort is applied and the resultant array is

-1 -2 -4 0 1 3 4

Next 'i' value is fixed to first element: -1

'j' value is fixed to 2nd element : -2

now binary search sarts x is 3rd index value:a[2]=-4 y is last index value

   mid= (2 + 6)/2=4

   mid is 4th element :a[mid]=1

   so,sum = -1 +-2 + 1= -2 <0

   consider higher value

x=mid+1=5th element

   Again calculate mid , mid=5+6/2=6 a[mid]=4

   sum= -1 + -2 + 4 = 1 >0

in the above way we will calculate the triplet values and verify that value equal to 0 or not

Hence the above algorithm will give correct number of triplets

c)Merge sort :O(nlogn ) ------------------- worst case time complexity

finding triplet :

1st for loop will run for 'n' times

2nd for loop will run for 'n' times

next finding mid and eleminating half values using binary search takes time of 'log n'

time complexity for triplet is : n*n*log n = n2 log n

  Hence,Total time complexity = nlog n + n2 log n= n2 log n

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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