Interview Question
Country: India
int findTriplet(int *arr,int size)
{
int a,b,c;
c=size-1;
while(c>1)
{
a=0;b=c-1;
while(a<b)
{
if(arr[a]*arr[a]+arr[b]*arr[b]==arr[c]*arr[c])
{
printf("%d %d %d\n",arr[a],arr[b],arr[c]);
a++;b--;
}
else if(arr[a]*arr[a]+arr[b]*arr[b]<arr[c]*arr[c])
a++;
else
b--;
}
c--;
}
}
Complete code here: ideone.com/Z3B5O
Well, you could do it in O(n^2). I'm assuming positive integers here for simplicity. First, sort the array. Then, In the equality a^2 + b^2 = c^2, try every element for c. Now for each choice of c, have two pointers, one initially pointing to the smallest element and one pointing to the element right before c. Let the first pointer be a and the second be b. Compute a^2 + b^2 for this choice of a, b and compare to c^2. If a^2 + b^2 = c^2, you're done. If a^2 + b^2 > c^2, decrement the b pointer. If a^2 + b^2 < c^2, increment the a pointer. if the two pointers meet, there are no a,b that satisfy the equality for the current choice of c.
- eugene.yarovoi July 20, 2012Since given a particular choice of c, you're shrinking the distance between the two pointers by 1 every time and that distance was at most O(n) to begin with, each choice of c is evaluated in O(n) time. Since there are O(n) choices of c, the algorithm is O(n^2).
Beating O(n^2) is probably very difficult because even for the (presumably) simpler problem of finding three numbers satisfying a + b = c, it is an open research problem whether a subquadratic time algorithm exists.