problem no 48:sorting problem:find the triplet inside the array that sum up to the given particular value.

 QUESTION:

Triplet Sum in Array

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

Popular posts from this blog

problem 3: given two integers N and M. The problem is to find the number closest to N and divisible by M. If there are more than one such number, then output the one having maximum absolute value.

problem no 7:Given two numbers A and B, find Kth digit from right of AB.

Problem no 16: count the number of squares below N.