Be the first user to complete this post

  • 0
Add to List
Beginner

237. Find three elements in an array that sum to a zero

Objec­tive:  Given an array of integers write an algorithm to find 3 elements that sum to a zero. In short a+b+c = 0.

Example

int [] = { 3,-1,-7,-4,-5,9,10};
Elements are -4 9 -5

Approach: Brute Force

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

Time Complexity: O(n^3)

 



public class Main { public static void find(int [] a){ for (int i = 0; i <a.length ; i++) { for (int j = i+1; j <a.length ; j++) { for (int l = j+1; l <a.length ; l++) { if(a[i]+a[j]+a[l]==0){ System.out.println("Found 3 elements whose sum is = 0"); System.out.println("Elements are " + a[i] + " " + a[j]+ " " + a[l]); return; } } } } System.out.println("Did not find 3 elements whose sum is = 0"); } public static void main(String[] args) { int a [] = { 3,-1,-7,-4,-5,9,10}; find(a); } }



def find(arr): for i in range(len(arr)): for j in range(i + 1, len(arr)): for l in range(j + 1, len(arr)): if arr[i] + arr[j] + arr[l] == 0: print("Found 3 elements whose sum is 0") print(f"Elements are {arr[i]} {arr[j]} {arr[l]}") return print("Did not find 3 elements whose sum is 0") if __name__ == "__main__": a = [3, -1, -7, -4, -5, 9, 10] find(a)



package main import "fmt" func find(arr []int) { for i := 0; i < len(arr); i++ { for j := i + 1; j < len(arr); j++ { for l := j + 1; l < len(arr); l++ { if arr[i]+arr[j]+arr[l] == 0 { fmt.Println("Found 3 elements whose sum is 0") println("Elements are", arr[i], arr[j], arr[l]) return } } } } fmt.Println("Did not find 3 elements whose sum is 0") } func main() { a := []int{3, -1, -7, -4, -5, 9, 10} find(a) }

Approach: Sorting

Time Complexity: O(n^2)

 



import java.util.Arrays; public class Main { //need to find a + b + c = 0 //OR we can reduce the problem to b + c = -a public static void find(int [] x){ Arrays.sort(x); for (int i = 0; i <x.length ; i++) { int a = x[i]; //now problem is reduced to find two numbers in an array whose sum = -a int sum = -a; int start = i + 1; int end = x.length-1; while(start<end){ int tempSum = x[start] + x[end]; if(tempSum==sum){ System.out.println("Found 3 elements whose sum is = 0"); System.out.println("Elements are " + a + " " + x[start]+ " " + x[end]); return; }else if(tempSum<sum) start++; else //tempSum>sum end--; } } } public static void main(String[] args) { int a [] = { 3,-1,-7,-4,-5,9,10}; find(a); } }



def find(arr): arr.sort() for i in range(len(arr)): a = arr[i] # now the problem is reduced to finding two numbers in an array whose sum = -a s = -a start, end = i + 1, len(arr) - 1 while start < end: temp_sum = arr[start] + arr[end] if temp_sum == s: print("Found 3 elements whose sum is 0") print(f"Elements are {a} {arr[start]} {arr[end]}") return elif temp_sum < s: start += 1 else: # temp_sum > s end -= 1 print("Did not find 3 elements whose sum is 0") if __name__ == "__main__": a = [3, -1, -7, -4, -5, 9, 10] find(a)



package main import ( "fmt" "sort" ) func find(x []int) { sort.Ints(x) for i := 0; i < len(x); i++ { a := x[i] // now the problem is reduced to finding two numbers in an array whose sum = -a s := -a start, end := i+1, len(x)-1 for start < end { tempSum := x[start] + x[end] if tempSum == s { fmt.Println("Found 3 elements whose sum is 0") fmt.Println("Elements are" , a, x[start], x[end]) return } else if tempSum < s { start++ } else { // tempSum > s end-- } } } fmt.Println("Did not find 3 elements whose sum is 0") } func main() { a := []int{3, -1, -7, -4, -5, 9, 10} find(a) }

Approach: Use Hashing

  • Use the other loop to fix the one element at a time.
  • Now required_sum is (with two elements) = -fixed element.
  • Create a HashSet, Iterate through the 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)

 



import java.util.HashSet; public class Main { //we need to find a + b + c = 0 //OR reduce the problem c = -(a+b) public static void find(int [] x){ for (int i = 0; i <x.length ; i++) { int a = x[i]; HashSet<Integer> set = new HashSet<Integer>(); for (int j=i+1; j<x.length; j++) { int b = x[j]; int c = -(a+b); if(set.contains(c)){ System.out.println("Found 3 elements whose sum is = 0"); System.out.println("Elements are " + a + " " + b + " " + c); return; }else set.add(b); } } } public static void main(String[] args) { int a [] = { 3,-1,-7,-4,-5,9,10}; find(a); } }



def find(x): for i in range(len(x)): a = x[i] number_set = set() for j in range(i + 1, len(x)): b = x[j] c = -(a + b) if c in number_set: print("Found 3 elements whose sum is 0") print(f"Elements are {a} {b} {c}") return else: number_set.add(b) print("Did not find 3 elements whose sum is 0") def main(): a = [3, -1, -7, -4, -5, 9, 10] find(a) if __name__ == "__main__": main()



package main func find(x []int) { for i := 0; i < len(x); i++ { a := x[i] numberSet := make(map[int]struct{}) for j := i + 1; j < len(x); j++ { b := x[j] c := -(a + b) if _, found := numberSet[c]; found { println("Found 3 elements whose sum is 0") println("Elements are", a, b, c) return } else { numberSet[b] = struct{}{} } } } println("Did not find 3 elements whose sum is 0") } func main() { a := []int{3, -1, -7, -4, -5, 9, 10} find(a) }

Output:

Found 3 elements whose sum is = 0
Elements are -4 9 -5