Closest Sum

Moderate

0/80

Average time to solve is 30m

Contributed by

55 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1

Sample Output 1

2 
9

Explanation of Sample Input 1

Test Case 1:
Sum of triplets:
(-1) + 2 + 1 = 2
(-1) + 2 + (-4) = -3
2 + 1 + (-4) = -1
(-1) + 1 + (-4) = -4
Out of all the triplet sums, 2 is closest to 1.

Test Case 2: Sum of triplet {2, 3, 4 } i.e. 9 is the closest sum to 10.

Sample Output 2

2
5
10 12 7 8 -5
16
4
6 8 2 5
20

Sample Output 2

15
19

Hint 1

Hint 2

Explore all combinations of 3 integers.

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

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.

Time Complexity

O(N^3), where ‘N’ is the number of elements in the array.

There are three nested loops traversing the array, so the time complexity is O(N * N * N) = O(N^3).

Space Complexity

O(1)

Constant extra space is required.

(100% EXP penalty)

Closest Sum

Console