Wednesday, June 10, 2015

Carwale Question: Find a triplet in an array that sum to given value

Problem: Given an array and a value, find if there is a triplet in array whose sum is equal to the given value.

Solution: Use sorting.

Implementation:

void findTriplet(int arr[], int len, int sum)
{
if(len < 3)
{
std::cout<<"Length is less than three\n";
return;
}
std::sort(arr, arr + len);

for(int i = 0; i < len - 2; ++i)
{
int left = i + 1, right = len - 1;
while(left < right)
{
int currSum = arr[i] + arr[left] + arr[right];
if(currSum == sum)
{
std::cout<<"Found Triplet:: "<<arr[i]<<' '<<arr[left]<<' '<<arr[right]<<'\n';
return;
}
else if(currSum < sum)
++left;
else
--right;
}
}

std::cout<<"Triplet not found\n";
}

Complexity: O(n2)

No comments:

Post a Comment