# finding three elements in an array whose sum is equal to a given number

April 19, 2013 3 Comments

Finding three elements in an array whose sum is equal to a given number(say trisum)

Here, for every element(arr[i]) that we pick, trisum-arr[i] gives us the bisum (algorithm to find a pair of elements that matches to sum k), hence we make use of our bisum algorithm to find a pair that matches to sum k

**Assumption: **The input array is sorted.

**Example **

arr: {1,2,3,4,5} and trisum is 8 then tri pairs are 1,3,4 and 1,2,5

Here lets say arr[i] is 1 then bisum=trisum-arr[i] i.e, bisum=8-1=7 therefore we should run bisum algorithm for sum 7

Time complexity for this algo: O(n^2) because for every element we need to find set of pairs

**Note:** If the array is not sorted the the complexity would be nlogn + O(n^2)

/** * find 3 elements in an array, that sum up to particular number with best * complexity * * @author ntallapa * */ public class TriPairSumCloseToK { public void getTriPair(int[] arr, int expectedTriSum) { for (int i = 0; i < arr.length; i++) { int expectedBiSum = expectedTriSum - arr[i]; String output = getPair2(arr, expectedBiSum, i); if(!output.equalsIgnoreCase("")) { System.out.println(arr[i]+","+output.toString()); } } } /** * Find the pair in an array whose sum with complexity O(n). This assumes * the array passed is sorted array and there are no duplicates in the * array * @param arr * input array of elements * @param expectedBiSum * sum for which pair of array elements needs to be searched */ public String getPair2(int[] arr, int expectedBiSum, int ignoreIndex) { int start = 0; int end = arr.length - 1; int sum = 0; // output array to record matching pairs StringBuilder arrs = new StringBuilder(); while (start < end) { // if(start == ignoreIndex) start++; // if(end == ignoreIndex) end--; sum = arr[start] + arr[end]; if (sum == expectedBiSum) { // we have found one pair, add it to our output array arrs.append(arr[start] + "," + arr[end] + ";"); start++; end--; } else if (sum < expectedBiSum) { // if the sum of the pair is less than the sum we are searching // then increment the start pointer which would give us the sum // more than our current sum as the array is sorted start++; } else { // if the sum of the pair is greater than the sum we are // searching then decrement the end pointer which would give us // the sum less than our current sum as the array is sorted end--; } } return arrs.toString(); } /** * Client to test * * @param args */ public static void main(String[] args) { TriPairSumCloseToK p = new TriPairSumCloseToK(); // sorted array algo int[] arr1 = { 1, 2, 3, 4, 5 }; p.getTriPair(arr1, 1); } }

Wow! This is often a particular of the very beneficial blogs We’ve ever before appear around about this topic. Generally Impressive. We are also an expert within this matter in order to comprehend your energy.

thank you hilton6l1t

public static void findPairs(int arr[] , int n){

int r[] = new int[3];

for(int i=0; i<arr.length ;i++){

if(arr[i]< n){

r[0]=arr[i];

for(int j=0; j<arr.length && (j != i) ; j++ ){

if(r[0]+arr[j] < n){

r[1]=arr[j];

for(int k=0; k<arr.length &&( k != i ) && ( k!= j);k++){

if(r[0]+r[1]+arr[k] == n){

r[2]= arr[k];

System.out.println("pair :"+ r[0]+" "+r[1]+" "+r[2]);

}

}

}

}

}

}

}

public static void main(String[] args) {

int arr[] = {2,4,8,1,6,9,3 ,1 };

findPairs(arr , 16 );

}