Be the first user to complete this post
|
Add to List |
237. Find three elements in an array that sum to a zero
Objective: 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
- Sort the array.
- Use the other loop to fix the one element at a time, say its ‘a’.
- Now the problem is reduced to "Find a pair of numbers from an array whose sum equals to K"
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