Given an array arr[] of N integers and an integer X, the task is to find three integers in arr[] such that the sum is closest to X.

 🎙 Asked in Google

Given an array arr[] of N integers and an integer X, the task is to find three integers in arr[] such that the sum is closest to X.

To solve this problem, we can follow the below approach:

• Sort the array arr[] in non-decreasing order.
• Initialize a variable diff with a very large value.
• Traverse the array arr[] from the start and for each element arr[i], find two elements in the remaining array (arr[i+1] to arr[n-1]) such that their sum is closest to (X - arr[i]).
• Keep updating diff with the minimum absolute difference between (X - arr[i]) and the sum of the triplet (arr[i], a, b) obtained in the previous step.
• Return (X - diff) as the closest sum.

Here is the Python code implementation for the above approach

program code :

In the above code,

we have used two pointers (left and right) to find two elements in the remaining array (arr[i+1] to arr[n-1]) such that their sum is closest to (X - arr[i]). We have also maintained the minimum absolute difference (diff) between (X - arr[i]) and the sum of the triplet (arr[i], a, b) obtained so far. Finally, we have returned the closest sum (X - diff).