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.

About these ads

Pages: 1 2

14 Responses to “4SUM”

  1. uberlazy said
    (defn- sum4* [coll so-far]
      (cond (empty? coll) nil
    	(= (count so-far) 4)
    	(if (= 0 (reduce + so-far))
    	    [so-far]
    	    nil)
    	:else
    	(concat (sum4* (rest coll) so-far)
    	        (sum4* coll (cons (first coll) so-far)))))
    
    (defn sum4 [coll]
      (sum4* coll []))
    
  2. […] today’s Programming Praxis exercise, our goal is to find four integers in a given list that sum up to a […]

  3. 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]
    
  4. Mike said

    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
    
  5. madscifi said

    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;
    }
    
  6. 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)))
    
    
  7. Jarvis said

    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.

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

  9. cosmin said

    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 None
    
  10. Ankit Thakur said

    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;
    }

    }

  11. David said

    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))
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 642 other followers

%d bloggers like this: