4SUM
August 14, 2012
We have today another exercise from our inexhaustible stock of interview questions:
Given an array of integers, output a list of four integers that sum to zero (the same input integer can be used multiple times), or indicate that no such set of four integers exists. For example, given the array (2 3 1 0 -4 -1), the set of four integers (3 1 0 -4) sums to zero, as does the set (0 0 0 0).
Your task is to write a program that solves the interview question. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
[…] today’s Programming Praxis exercise, our goal is to find four integers in a given list that sum up to a […]
My Haskell solution (see http://bonsaicode.wordpress.com/2012/08/14/programming-praxis-4sum/ for a version with comments):
import qualified Data.IntMap as I sum4 :: Int -> [Int] -> [[Int]] sum4 n xs = take 1 [p1++p2 | (s, p1) <- I.assocs pairs , p2 <- maybe [] return $ I.lookup (n-s) pairs] where pairs = I.fromList [(a+b, [a,b]) | a <- xs, b <- xs]Solution in Kawa Scheme:
4-SUM on Codepad
Python
from itertools import combinations_with_replacement def sumof4(nums, tgt=0): rems = {} for c, d in combinations_with_replacement(nums, r=2): s = c + d if s in rems: a, b = rems[s] return a, b, c, d else: rems[tgt - s] = c, d return None[…] Pages: 1 2 […]
Requires -std=c++0x option when compiled with g++.
#include <iostream> #include <map> #include <list> template<class IT, class VT = typename std::iterator_traits<IT>::value_type> std::list<VT> sum4( IT a, IT aend ) { std::map< VT, std::pair<VT, VT> > amap; for( IT i = a; i != aend; ++i ) { for( IT j = i; j != aend; ++j ) { amap[ *i + *j ] = std::make_pair( *i, *j ); auto iter = amap.find( -(*i + *j) ); if( iter != amap.end() ) { return std::list<VT> { *i, *j, iter->second.first, iter->second.second }; } } } return std::list<VT>(); } int main( int argc, char**argv ) { std::list<int> a = { 2, 3, 1, 0, -4, -1 }; auto r = sum4( std::begin(a), std::end(a) ); if( !r.empty() ) { for( auto i : r ) std::cout << i << " "; std::cout << std::endl; } else { std::cout << "no items 4 sum to zero" << std::endl; } return 0; }An inefficient solution in Common Lisp.
Another Clojure solution:
(ns programming_praxis.core (:use clojure.contrib.combinatorics)) (defn collect-if-solution [pair sum sums solutions] (if (contains? sums (- sum)) (conj solutions (sort (concat pair (get sums (- sum))))) solutions)) (defn four-sum [nums] (loop [sums {} pairs (selections nums 2) solutions ()] (if (empty? pairs) (distinct solutions) (let [pair (first pairs) sum (apply + pair)] (recur (assoc sums sum pair) (rest pairs) (collect-if-solution pair sum sums solutions)))))) (println (four-sum '(2 3 1 0 -4 1)))program foursum;
var bil:array [1..1000] of integer;
test:array [1..4] of integer;
i,j,k,l:integer;
procedure testing;
var cc,hasil:integer;
begin
hasil:=0;
for cc:= 1 to 4 do hasil:=hasil+test[cc];
if hasil = 0 then begin
for cc:= 1 to 4 do write(test[cc],’ ‘);
writeln;
end;
end;
procedure permut(xx:integer);
var hasil,bb:integer;
begin
if xx = 4 then begin
for bb:= 1 to i do begin
test[4]:= bil[bb];
testing;
end;
end
else
begin
for bb:= 1 to i do begin
test[xx]:=bil[bb];
permut(xx+1);
end;
end;
end;
begin
i := 0;
while not eof do begin
inc(i);
read(bil[i]);
end;
permut(1);
end.
[…] One more from Programming Praxis, this time we’re dealing with summing combinations of a sequence. More formally, given a secquence S, either choose four elements s1 through s4 from S such that s1+s2+s3+s4 = 0 or verify that it isn’t possible. This immediately makes me about working through possible solutions until we find one and then bailing out, ergo call/cc: (define (4sum ls) (call/cc (lambda (exit) (for-each (lambda (i) (for-each (lambda (j) (for-each (lambda (k) (for-each (lambda (l) (when (= 0 (+ i j l k)) (exit (list i j k l)))) ls)) ls)) ls)) ls) (exit #f)))) […]
Another Python solution:
def zeroSum(numbers): dictionary = {} for a in numbers: for b in numbers: dictionary[a+b] = [a, b] if -(a+b) in dictionary: [c, d] = dictionary[-(a+b)] return [a, b, c, d] return Noneimport java.io.*;
import java.util.ArrayList;
public class combination {
ArrayList values=new ArrayList();
public void problem1()
{
try
{
ArrayList array=new ArrayList();
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
System.out.println(“Input the size of array”);
int number=(Integer.parseInt(br.readLine()));
for(int count=1;count<=number;count++)
{
System.out.println("Input the elements of array");
int value=Integer.parseInt(br.readLine());
array.add(value);
}
for(int count1=0;count1<array.size();count1++)
{
for(int count2=0;count2<array.size();count2++)
{
for(int count3=0;count3<array.size();count3++)
{
for(int count4=0;count4<array.size();count4++)
{
if(sum(array.get(count1),array.get(count2),array.get(count3),array.get(count4)))
{
if(check(array.get(count1),array.get(count2),array.get(count3),array.get(count4)))
{
values.add(array.get(count1)+","+array.get(count2)+","+array.get(count3)+","+array.get(count4));
}
}
}
}
}
}
if(values.size()==0)
{
System.out.println("No elements Present");
}
else
System.out.println(values);
}
catch(IOException ioe)
{
ioe.printStackTrace();
}
}
public boolean sum(int num1,int num2,int num3,int num4)
{
if(num1+num2+num3+num4==0)
return true;
else
return false;
}
public boolean check(int value1,int value2,int value3,int value4)
{
ArrayList number_present=new ArrayList();
number_present.add(value1);
number_present.add(value2);
number_present.add(value3);
number_present.add(value4);
for(String used_number:values)
{
ArrayList number_present_copy=new ArrayList(number_present);
String number[]=used_number.split(“,”);
for(int count=0;count<number.length;count++) //each number counter
{
for(int i=0;i<number_present_copy.size();i++)
{
if(number[count].equals(Integer.toString(number_present_copy.get(i))))
{
number_present_copy.remove(i);
break;
}
}
}
if(number_present_copy.size()==0)
return false;
}
return true;
}
}
Lacking any insight, in Python:
import sys sys.setrecursionlimit(10000) def divide(v1): x = [] y = [] zed = False for i in v1: if i < 0: y.append(i) elif i > 0: x.append(i) elif i == 0: zed = True x.sort() x.reverse() y.sort() return x, y, zed def walk(x, y, l): if len(l) == 4 and sum(l) == 0: return l elif len(l) == 4: return False elif len(l) == 3 and sum(l) == 0: return False if sum(l) > 0: for n in y: result = walk(x, y, l + [n,]) if result and sum(result) == 0: return result if sum(l) < 0: for n in x: result = walk(x, y, l + [n,]) if result and sum(result) == 0: return result return False def process(v1): x, y, z = divide(v1) if z: return [0,]*4 if not x or not y: return [] y *= 4 x *= 4 for n in xrange(len(x)): result = walk(x, y, [x[n]]) if result and sum(result) == 0: return result for n in xrange(len(y)): result = walk(x, y, [y[n]]) if result and sum(result) == 0: return result print process((2, 3, 1, -4, -1))[…] 4SUM […]