finding a triplet having a given sum

Question

Hi,

I have been struggling with this questions for sometime now. The question goes like this:-

We have n^2 numbers. We need to find out if there exists a triplet a,b,c such that a+b+c = 0. For a more generic case, a+b+c = k. (k is given)

There exists a solution with O(n^2log(n)) complexity.

Any help would be greatly appreciated.

thanks

Answer 1

See if this helps.

Answer 2

To get this in O(n²logn), you'd have to sort the numbers. Find all combinations of 2 numbers, and do a binary search to find the third.

The upper bound is much higher for the general version of the problem.