Last Updated: 12 Nov, 2020
Closest Sum
Moderate
Asked in companies
Given an array 'ARR'' of 'N' integers and an integer 'target', your task is to find three integers in 'ARR' such that the sum is closest to the target.
Note
In the case of two closest sums, print the smallest sum.
Input Format
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then, the T test cases follow.
The first line of each test case or query contains an integer 'N' representing the size of the array.
The second line contains 'N' single space-separated integers, representing the elements in the array.
The third line contains the value of the target.
Output Format
For each test case, print the sum of triplets closest to the target.
Print the output of each test case in a new line.
Note
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
3 <= N <= 100
-10^5 <= Arr[i] <= 10^5
-3 * 10^5 <= target <= 3 * 10^5
where Arr[i] refers to the elements of the array.
Time Limit: 1 sec
Approaches
The approach is to explore all the subsets of size 3 and keep a track of the difference between the target value and the sum of this subset. Then return the sum which is the closest to the target.
- Create three nested loops with counter i, j and k respectively.
- The first loop will run from 0 to N-1, the second loop will run from i+1 to N-1 and the third loop will run from j+1 to N-1.
- Check if the absolute difference of the sum of ith, jth and kth element and the value of the target is less than the absolute difference of the current value of closest sum and the value of the target. Update the closest sum if required.
- Print the closest sum.
By sorting the array the efficiency of the algorithm can be improved. This efficient approach uses the two-pointer technique.
After sorting the array, traverse the array and fix the first element of the triplet. Now use the Two Pointers algorithm to find the closest number to target - Arr[i], where i is the index of the current element of the array. Update the closest sum. Two-pointers algorithm takes linear time, so it is better than a nested loop.
Two - Pointer algorithm :
We take two pointers, one representing the first element and the other representing the last element of the array, and then we add the values kept at both the pointers. If their sum is smaller than the target then we shift the left pointer to right and if their sum is greater than the target then we shift the right pointer to left, in order to get closer to the target.
Algorithm
- Sort the given array.
- Loop over the array and fix the first element of the possible triplet, Arr[i].
- Then fix two pointers, one at i+1 and the other at N-1. Now consider the sum Arr[i+1] + Arr[n-1],
- If the sum is smaller than target - Arr[i], we increase the first pointer.
- Else, if the sum is greater than target - Arr[i], decrease the end pointer to reduce the sum.
- Update the closest sum found so far.
Similar problems