## 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.

Advertisements

[…] 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):

Solution in Kawa Scheme:

4-SUM on Codepad

Python

[…] Pages: 1 2 […]

Requires -std=c++0x option when compiled with g++.

An inefficient solution in Common Lisp.

Another Clojure solution:

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:

import 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:

[…] 4SUM […]