Given an array of integers, A1, A2, ..., An, including negatives and positives, and another integer S. Now we need to find three different integers in the array, whose sum is closest to the given integer S. If there exists more than one solution, any of them is ok.
You can assume all the integers are within int32_t range, and no arithmetic overflow will occur with calculating the sum. S is nothing special but a randomly picked number.
Is there any efficient algorithm other than brute force search to find the three integers?
How about something like this, which is O(n^2)
for(each ele in the sorted array)
{
ele = arr[i] - YOUR_NUMBER;
let front be the pointer to the front of the array;
let rear be the pointer to the rear element of the array.;
// till front is not greater than rear.
while(front <= rear)
{
if(*front + *rear == ele)
{
print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
break;
}
else
{
// sum is > ele, so we need to decrease the sum by decrementing rear pointer.
if((*front + *rear) > ele)
decrement rear pointer.
// sum is < ele, so we need to increase the sum by incrementing the front pointer.
else
increment front pointer.
}
}
This finds if sum of 3 elements is exactly equal to your number. If you want closest, you can modify it to remember the smallest delta(difference between your number of current triplet) and at the end print the triplet corresponding to smallest delta.
Here is the Python3 code
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
result = set()
nums.sort()
L = len(nums)
for i in range(L):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1,L):
if j > i + 1 and nums[j] == nums[j-1]:
continue
l = j+1
r = L -1
while l <= r:
sum = nums[i] + nums[j] + nums[l]
result.add(sum)
l = l + 1
while l<=r and nums[l] == nums[l-1]:
l = l + 1
result = list(result)
min = result[0]
for i in range(1,len(result)):
if abs(target - result[i]) < abs(target - min):
min = result[i]
return min
Reduction : I think @John Feminella solution O(n2) is most elegant. We can still reduce the A[n] in which to search for tuple. By observing A[k] such that all elements would be in A[0] - A[k], when our search array is huge and SUM (s) really small.
A[0] is minimum :- Ascending sorted array.
s = 2A[0] + A[k] : Given s and A[] we can find A[k] using binary search in log(n) time.
The problem can be solved in O(n^2) by extending the 2-sum problem with minor modifications.A is the vector containing elements and B is the required sum.
int Solution::threeSumClosest(vector &A, int B) {
sort(A.begin(),A.end());
int k=0,i,j,closest,val;int diff=INT_MAX;
while(k<A.size()-2)
{
i=k+1;
j=A.size()-1;
while(i<j)
{
val=A[i]+A[j]+A[k];
if(val==B) return B;
if(abs(B-val)<diff)
{
diff=abs(B-val);
closest=val;
}
if(B>val)
++i;
if(B<val)
--j;
}
++k;
}
return closest;
John Feminella's solution has a bug.
At the line
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
We need to check if i,j,k are all distinct. Otherwise, if my target element is 6 and if my input array contains {3,2,1,7,9,0,-4,6} . If i print out the tuples that sum to 6, then I would also get 0,0,6 as output . To avoid this, we need to modify the condition in this way.
if ((A[i] + A[j] + A[k] == 0) && (i!=j) && (i!=k) && (j!=k)) return (A[i], A[j], A[k])
Very simple N^2*logN solution: sort the input array, then go through all pairs Ai, Aj (N^2 time), and for each pair check whether (S - Ai - Aj) is in array (logN time).
Another O(S*N) solution uses classical dynamic programming approach.
In short:
Create an 2-d array V[4][S + 1]. Fill it in such a way, that:
V[0][0] = 1, V[0][x] = 0;
V1[Ai]= 1 for any i, V1[x] = 0 for all other x
V[2][Ai + Aj]= 1, for any i, j. V[2][x] = 0 for all other x
V[3][sum of any 3 elements] = 1.
To fill it, iterate through Ai, for each Ai iterate through the array from right to left.
Here is the program in java which is O(N^2)
import java.util.Stack;
public class GetTripletPair {
/** Set a value for target sum */
public static final int TARGET_SUM = 32;
private Stack<Integer> stack = new Stack<Integer>();
/** Store the sum of current elements stored in stack */
private int sumInStack = 0;
private int count =0 ;
public void populateSubset(int[] data, int fromIndex, int endIndex) {
/*
* Check if sum of elements stored in Stack is equal to the expected
* target sum.
*
* If so, call print method to print the candidate satisfied result.
*/
if (sumInStack == TARGET_SUM) {
print(stack);
}
for (int currentIndex = fromIndex; currentIndex < endIndex; currentIndex++) {
if (sumInStack + data[currentIndex] <= TARGET_SUM) {
++count;
stack.push(data[currentIndex]);
sumInStack += data[currentIndex];
/*
* Make the currentIndex +1, and then use recursion to proceed
* further.
*/
populateSubset(data, currentIndex + 1, endIndex);
--count;
sumInStack -= (Integer) stack.pop();
}else{
return;
}
}
}
/**
* Print satisfied result. i.e. 15 = 4+6+5
*/
private void print(Stack<Integer> stack) {
StringBuilder sb = new StringBuilder();
sb.append(TARGET_SUM).append(" = ");
for (Integer i : stack) {
sb.append(i).append("+");
}
System.out.println(sb.deleteCharAt(sb.length() - 1).toString());
}
private static final int[] DATA = {4,13,14,15,17};
public static void main(String[] args) {
GetAllSubsetByStack get = new GetAllSubsetByStack();
get.populateSubset(DATA, 0, DATA.length);
}
}
This can be solved efficiently in O(n log (n)) as following. I am giving solution which tells if sum of any three numbers equal a given number.
import java.util.*;
public class MainClass {
public static void main(String[] args) {
int[] a = {-1, 0, 1, 2, 3, 5, -4, 6};
System.out.println(((Object) isThreeSumEqualsTarget(a, 11)).toString());
}
public static boolean isThreeSumEqualsTarget(int[] array, int targetNumber) {
//O(n log (n))
Arrays.sort(array);
System.out.println(Arrays.toString(array));
int leftIndex = 0;
int rightIndex = array.length - 1;
//O(n)
while (leftIndex + 1 < rightIndex - 1) {
//take sum of two corners
int sum = array[leftIndex] + array[rightIndex];
//find if the number matches exactly. Or get the closest match.
//here i am not storing closest matches. You can do it for yourself.
//O(log (n)) complexity
int binarySearchClosestIndex = binarySearch(leftIndex + 1, rightIndex - 1, targetNumber - sum, array);
//if exact match is found, we already got the answer
if (-1 == binarySearchClosestIndex) {
System.out.println(("combo is " + array[leftIndex] + ", " + array[rightIndex] + ", " + (targetNumber - sum)));
return true;
}
//if exact match is not found, we have to decide which pointer, left or right to move inwards
//we are here means , either we are on left end or on right end
else {
//we ended up searching towards start of array,i.e. we need a lesser sum , lets move inwards from right
//we need to have a lower sum, lets decrease right index
if (binarySearchClosestIndex == leftIndex + 1) {
rightIndex--;
} else if (binarySearchClosestIndex == rightIndex - 1) {
//we need to have a higher sum, lets decrease right index
leftIndex++;
}
}
}
return false;
}
public static int binarySearch(int start, int end, int elem, int[] array) {
int mid = 0;
while (start <= end) {
mid = (start + end) >>> 1;
if (elem < array[mid]) {
end = mid - 1;
} else if (elem > array[mid]) {
start = mid + 1;
} else {
//exact match case
//Suits more for this particular case to return -1
return -1;
}
}
return mid;
}
}
Another solution that checks and fails early:
public boolean solution(int[] input) {
int length = input.length;
if (length < 3) {
return false;
}
// x + y + z = 0 => -z = x + y
final Set<Integer> z = new HashSet<>(length);
int zeroCounter = 0, sum; // if they're more than 3 zeros we're done
for (int element : input) {
if (element < 0) {
z.add(element);
}
if (element == 0) {
++zeroCounter;
if (zeroCounter >= 3) {
return true;
}
}
}
if (z.isEmpty() || z.size() == length || (z.size() + zeroCounter == length)) {
return false;
} else {
for (int x = 0; x < length; ++x) {
for (int y = x + 1; y < length; ++y) {
sum = input[x] + input[y]; // will use it as inverse addition
if (sum < 0) {
continue;
}
if (z.contains(sum * -1)) {
return true;
}
}
}
}
return false;
}
I added some unit tests here: GivenArrayReturnTrueIfThreeElementsSumZeroTest.
If the set is using too much space I can easily use a java.util.BitSet that will use O(n/w) space.
Note that we have a sorted array. This solution is similar to John's solution only that it looks for the sum and does not repeat the same element.
#include <stdio.h>;
int checkForSum (int arr[], int len, int sum) { //arr is sorted
int i;
for (i = 0; i < len ; i++) {
int left = i + 1;
int right = len - 1;
while (right > left) {
printf ("values are %d %d %d\n", arr[i], arr[left], arr[right]);
if (arr[right] + arr[left] + arr[i] - sum == 0) {
printf ("final values are %d %d %d\n", arr[i], arr[left], arr[right]);
return 1;
}
if (arr[right] + arr[left] + arr[i] - sum > 0)
right--;
else
left++;
}
}
return -1;
}
int main (int argc, char **argv) {
int arr[] = {-99, -45, -6, -5, 0, 9, 12, 16, 21, 29};
int sum = 4;
printf ("check for sum %d in arr is %d\n", sum, checkForSum(arr, 10, sum));
}
Here is the C++ code:
bool FindSumZero(int a[], int n, int& x, int& y, int& z)
{
if (n < 3)
return false;
sort(a, a+n);
for (int i = 0; i < n-2; ++i)
{
int j = i+1;
int k = n-1;
while (k >= j)
{
int s = a[i]+a[j]+a[k];
if (s == 0 && i != j && j != k && k != i)
{
x = a[i], y = a[j], z = a[k];
return true;
}
if (s > 0)
--k;
else
++j;
}
}
return false;
}
Program to get those three elements. I have just sorted the array/list first and them updated minCloseness based upon each triplet.
public int[] threeSumClosest(ArrayList<Integer> A, int B) {
Collections.sort(A);
int ansSum = 0;
int ans[] = new int[3];
int minCloseness = Integer.MAX_VALUE;
for (int i = 0; i < A.size()-2; i++){
int j = i+1;
int k = A.size()-1;
while (j < k){
int sum = A.get(i) + A.get(j) + A.get(k);
if (sum < B){
j++;
}else{
k--;
}
if (minCloseness > Math.abs(sum - B)){
minCloseness = Math.abs(sum - B);
ans[0] = A.get(i); ans[1] = A.get(j); ans[2] = A.get(k);
}
}
}
return ans;
}
certainly this is a better solution because it's easier to read and therefore less prone to errors. The only problem is, we need to add a few lines of code to avoid multiple selection of one element.
Another O(n^2) solution (by using a hashset).
// K is the sum that we are looking for
for i 1..n
int s1 = K - A[i]
for j 1..i
int s2 = s1 - A[j]
if (set.contains(s2))
print the numbers
set.add(A[i])
I did this in n^3, my pseudocode is below;
//Create a hashMap with key as Integer and value as ArrayList //iterate through list using a for loop, for each value in list iterate again starting from next value;
for (int i=0; i<=arr.length-1 ; i++){
for (int j=i+1; j<=arr.length-1;j++){
//if the sum of arr[i] and arr[j] is less than desired sum then there is potential to find a third digit so do another for loop
if (arr[i]+arr[j] < sum){
for (int k= j+1; k<=arr.length-1;k++)
//in this case we are now looking for the third value; if the sum of arr[i] and arr[j] and arr[k] is the desired sum then add these to the HashMap by making the arr[i] the key and then adding arr[j] and arr[k] into the ArrayList in the value of that key
if (arr[i]+arr[j]+arr[k] == sum){
map.put(arr[i],new ArrayList<Integer>());
map.get(arr[i]).add(arr[j]);
map.get(arr[i]).add(arr[k]);}
after this you now have a dictionary that has all the entries representing the three values adding to the desired sum. Extract all these entries using HashMap functions. This worked perfectly.
Source: Stackoverflow.com