problem no 48:sorting problem:find the triplet inside the array that sum up to the given particular value.
QUESTION:
Given an array arr of size arr_size and an integer sum. Find if there's a triplet in the array which sums up to the given integer sum.
Example 1:
Input:
N = 6, X = 13
arr[] = [1 4 45 6 10 8]
Output:
1
Explanation:
The triplet {1, 4, 8} in
the array sums up to 13.
Example 2:
Input:
N = 5, X = 10
arr[] = [1 2 4 3 6]
Output:
1
Explanation:
The triplet {1, 3, 6} in
the array sums up to 10.
ANSWER:
bool find3Numbers(int A[], int arr_size, int sum)
{
int l, r;
sort(A, A + arr_size);
for (int i = 0; i < arr_size - 2; i++) {
l = i + 1;
r = arr_size - 1;
while (l < r) {
if (A[i] + A[l] + A[r] == sum) {
return true;
}
else if (A[i] + A[l] + A[r] < sum)
l++;
else // A[i] + A[l] + A[r] > sum
r--;
}
}
// If we reach here, then no triplet was found
return false;
}
Comments
Post a Comment