# Find three elements in an array that sum to a given value

Objec­tive:  Given an array of integer write an algorithm to find 3 elements that sum to a given number k. In short a+b+c = k.

Example:

```int a [] = { 3,1,7,4,5,9,10} , k = 21;Output: Elements are 7 4 10 int a [] = { 3,1,7,4,5,9,10} , k = 55;Output: Did not find 3 elements whose sum is 55
```

Approach: Brute Force

Use 3 nested loops and find the 3 elements which sum to k.

Time Complexity: O(n^3)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 public class ThreeNumbersSumKBruteForce { public static void find(int [] a, int k){ for (int i = 0; i

Approach: Sorting

• Sort the array.
• Use the other loop to fix the one element at a time
• Now problem is reduced to “Find a pair of numbers from an array whose sum equals k”

Time Complexity: O(n^2)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.Arrays; public class ThreeNumbersSumKSorting { public static void find(int [] a, int k){ Arrays.sort(a); for (int i = 0; i M end—; } } } public static void main(String[] args) { int a [] = { 3,1,7,4,5,9,10}; int k = 21; find(a,k); } }

Approach: Use Hashing

• Use the other loop to fix the one element at a time.
• Now required_sum is (with two elements) = k-fixed element.
• Create a HashSet, Iterate through rest of the array.
• For current_element, remain_value = required_sum – current_element.
• Check if remain_value in the HashSet, we have found our triplets else add current_element to the hashset.

Time Complexity: O(n^2)

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.HashSet; public class ThreeNumbersSumKHashing { public static void find(int [] a, int k){ for (int i = 0; i map = new HashSet<>(); //assume all array elements are less than 99999 for (int j=start; j<=end; j++) { int remain = M–a[j]; // checking for condition if (remain>=0 && map.contains(remain)==true) { System.out.println("Found 3 elements whose sum is = " +k); System.out.println("Elements are " + a[i] + " " + a[j]+ " " + remain); return; } map.add(a[j]); } } } public static void main(String[] args) { int a [] = { 3,1,7,7,5,9,10}; int k = 22; find(a,k); } }

Output:

```Found 3 elements whose sum is = 22
Elements are 3 10 9```

This site uses Akismet to reduce spam. Learn how your comment data is processed.