original problem P:
Given an array A of n integers and a target value S, does there exist a 3-tuple from A that sums to S?
modified problem P':
Given an array A of n integers, does there exist a 3-tuple from A that sums to zero?
Or Finding three elements in an array whose sum is closest to an given number.
This is also known as the 3sum problem.
Clearly, if we simply test all possible 3-tuples, we'd solve the problem in O(n^3) -- that's the brute-force baseline. Is it possible to do better? What if we pick the tuples in a somewhat smarter way?
First, we invest some time to sort the array, which costs us an initial penalty of O(n log n). Now we execute this algorithm:
for (i in 1..n-2) {
j = i+1 // Start right after i.
k = n // Start at the end of the array.
while (k >= j) {
// We got a match! All done.
if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])
// We didn't match. Let's try to get a little closer:
// If the sum was too big, decrement k.
// If the sum was too small, increment j.
(A[i] + A[j] + A[k] > 0) ? k-- : j++
}
// When the while-loop finishes, j and k have passed each other and there's
// no more useful combinations that we can try with this i.
}
This algorithm works by placing three pointers, i, j, and k at various points in the array. i starts off at the beginning and slowly works its way to the end. k points to the very last element. j points to where i has started at. We iteratively try to sum the elements at their respective indices, and each time one of the following happens:
The sum is exactly right! We've found the answer.
The sum was too small. Move j closer to the end to select the next biggest number.
The sum was too big. Move k closer to the beginning to select the next smallest number.
For each i, the pointers of j and k will gradually get closer to each other. Eventually they will pass each other, and at that point we don't need to try anything else for that i, since we'd be summing the same elements, just in a different order. After that point, we try the next i and repeat.
Eventually, we'll either exhaust the useful possibilities, or we'll find the solution. You can see that this is O(n^2) since we execute the outer loop O(n) times and we execute the inner loop O(n) times. It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.
Code:
/***************************************************************************
* code in Italic font is used for finding Triplet closest to given sum.
* Ignore Italic font in case you don't want to solve closest sum problem.
***************************************************************************/
import java.io.*;
import java.util.*;
public class Sum3 {
static int result,a,b,c; // to store result of closest sum problem
static int len=0,sum=0;
private static int array[]=new int[len];
public static void main(String args[]) throws NumberFormatException, IOException
{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter length of array");
len =Integer.parseInt(br.readLine()); // take length of array from user
setArray(Arrays.copyOf(getArray(), getArray().length + len)); // reinitialize array to given length
System.out.println("Enter elements:"); // takes input
for(int i=0;i<len;i++)
getArray()[i]=Integer.parseInt(br.readLine());
System.out.println("Enter sum:");
sum =Integer.parseInt(br.readLine());
Sum3 s =new Sum3();
Quicksort q= new Quicksort();
q.sort(0, array.length-1); // to perform sorting
s.findTriplet(); // to find Triplet
System.out.println("\n\nTriplet closest to given sum "+result+" is (" +a+", "+b+", "+c+")");
}
void findTriplet()
{
int min =999999; // to store min for closest sum problem
for (int i = 0; i < array.length - 2; i++)
{
int j = i + 1;
int k = array.length-1;
while (j < k)
{
if( array[i] + array[j] + array[k] == sum)
{
System.out.println("Triplet with given sum "+sum+" is (" + array[i]+", "+array[j]+", "+array[k]+")");
break;
}
else
{
// code to calculate closest sum
int diff=Math.abs((array[i] + array[j] + array[k])-sum);
if(diff<min)
{
min=diff;
result=array[i] + array[j] + array[k];
a=array[i];
b=array[j];
c=array[k];
}
if (array[i] + array[j] + array[k] < sum)
j++;
else
k--;
}
}
}
}
/***************************************************************************
* functions to access array
***************************************************************************/
public static int[] getArray() { //return the array
return array;
}
public static void setArray(int array[]) { //@param array the array to set
Sum3.array = array;
}
}
/***************************************************************************
* Quicksort
***************************************************************************/
class Quicksort
{
static Sum3 s1 =new Sum3();
static Quicksort q1= new Quicksort();
void sort(int low,int high)
{
if(high<=low)
return;
int j=partition(low, high);
sort(low,j-1);
sort(j+1,high);
}
int partition(int low,int high)
{
int i=low;
int j=high+1;
int pivot=Sum3.getArray()[low];
while(true)
{
while(Sum3.getArray()[++i]<pivot)
if(i== high) break;
while(pivot<Sum3.getArray()[--j])
if(j==low) break;
if(i>=j) break;
q1.exchange(i,j);
}
q1.exchange(low,j);
return j;
}
void exchange(int i,int j)
{
int temp = Sum3.getArray()[i];
Sum3.getArray()[i]=Sum3.getArray()[j];
Sum3.getArray()[j]=temp;
}
}
/***************************************************************************
original problem P:
Given an array A of n integers and a target value S, does there exist a 3-tuple from A that sums to S?
modified problem P':
Finding three elements in an array whose sum is closest to an given number.
OUTPUT:
Enter length of array
8
Enter elements:
Enter length of array
8
Enter elements:
150
-50
70
-50
25
11
19
14
Enter sum:
50
Triplet with given sum 50 is (-50, -50, 150)
Triplet with given sum 50 is (11, 14, 25)
Triplet closest to given sum 45 is (-50, 25, 70)
modified problem P':
Given an array A of n integers, does there exist a 3-tuple from A that sums to zero?
modified problem P':
Finding three elements in an array whose sum is closest to an given number.
OUTPUT :
Enter length of array
8
Enter elements:
100
20
-50
-50
40
30
-70
-61
Enter sum:
0
Triplet with given sum 0 is (-70, 30, 40)
Triplet with given sum 0 is (-50, -50, 100)
Triplet with given sum 0 is (-50, 20, 30)
Triplet closest to given sum -1 is (-61, 20, 40)
***************************************************************************/