Sum Of Two Integers

July 19, 2011

We have today another exercise in our on-going series of interview questions:

Write a program that takes a list of integers and a target number and determines if any two integers in the list sum to the target number. If so, return the two numbers. If not, return an indication that no such integers exist.

Your task is to write the indicated program. 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

22 Responses to “Sum Of Two Integers”

  1. Graham said
    def quad(xs, t):
        l = len(xs)
        for i in xrange(l):
            for j in xrange(i + 1, l):
                if xs[i] + xs[j] == t:
                    return (xs[i], xs[j])
        return None
    
    def nlogn(xs, t):
        ys = sorted(xs)
        i, j = 0, len(ys) - 1
        while i != j:
            s = ys[i] + ys[j]
            if s == t:
                return (ys[i], ys[j])
            elif s < t:
                i += 1
            else:
                j -= 1
        return None
    
    def linear(xs, t):
        d = set()
        for x in xs:
            if t - x in d:
                return (t - x, x)
            else:
                d.add(x)
        return None
    
  2. Mike said
    """
    Prints the first pair of integers in list_of_integers that sum to target_sum.
    A blank line is printed if there is no such pair.
    
    The integers can be taken from the command line or standard input.
    """
    import sys
    
    def sumto(target, numbers):
        diff = {}
        for number in numbers:
            if number in diff:
                return diff[number], number
            else:
                diff[target-number] = number
    
    if __name__ == '__main__':
        if len(sys.argv) > 1:
            if any(arg.startswith('-') for arg in sys.argv[1:]):
                print __doc__
                exit()
    
            source = [' '.join(sys.argv[1:])]
            
        else:
            source = sys.stdin
    
        for line in source:
            numbers = map(int, line.split())
            result = sumto(numbers[0], numbers[1:])
    
            if result:
                sys.stdout.write('{} {}\n'.format(*result))
            else:
                sys.stdout.write('\n')
    
  3. slabounty said

    Ruby versions (plus simple test cases) …

    def twosum1(list, sum_value)
        0.upto(list.size-1) do |i| 
            i+1.upto(list.size-1) do |j| 
                if list[i] + list[j] == sum_value
                    return list[i], list[j]
                end
            end
        end
        return false
    end
    
    def twosum2(list, sum_value)
        list_sorted = list.sort
        i,j = 0, list_sorted.size-1
        while i != j do
            if list_sorted[i] + list_sorted[j] == sum_value
                return list_sorted[i], list_sorted[j]
            elsif list_sorted[i] + list_sorted[j] < sum_value
                i = i+1
            else
                j = j-1
            end
        end
        return false
    end
    
    def twosum3(list, sum_value)
        h = {}
        list.each do |v|
            if h.has_value?(sum_value-v)
                return v, sum_value-v
            else
                h[v] = v
            end
        end
        return false
    end
    
    a = [2, 3, 4, 5, 6]
    test_sum1 = 6
    test_sum2 = 4
    
    puts "test 1 = #{twosum1(a, test_sum1)}"
    puts "test 2 = #{twosum1(a, test_sum2)}"
    
    puts "test 1 = #{twosum2(a, test_sum1)}"
    puts "test 2 = #{twosum2(a, test_sum2)}"
    
    puts "test 1 = #{twosum3(a, test_sum1)}"
    puts "test 2 = #{twosum3(a, test_sum2)}"
    
    
  4. Ecodelta said

    Sort the numbers using a O(n log n) algorithm.

    Compare highest and lowest values in sorted list.

    If sum match target append to result list and delete both from sorted list

    If sum greater than target delete higher from sorted list

    If sum less than target delete lower from sorted list

    Continue until sorted list if empty or only one element is left.

  5. Stephen Lemp said

    Another Ruby solution, took it a bit further so it supports more than just addition.
    Turns out Ruby has a builtin solution too. [1,2,3,4,5].combination(2).select { |a,b| a + b == 3 }
    Anyway this was a fun exercise.

    class Array

    def pairs_with_match( &block )
    raise TypeError, ‘Error: list must be an array of integers.’ unless self.all? { |i| i.kind_of? Integer }

    results = self.each_with_object( [] ).with_index do |( current_number, result_array ), index|
    compare_array = self.drop(index)
    compare_array.each do |compare_number|
    result_array << [current_number, compare_number] if block.call( current_number, compare_number )
    end
    end
    results.empty? ? "There were no matches." : results
    end

    end

    test = (1..100).each_with_object( [] ) { |i, result_array| result_array << i }

    puts "\nAddition:\n"
    print test.pairs_with_match { |a,b| a + b == 108 }
    puts "\n\nSubtraction\n"
    print test.pairs_with_match { |a,b| b – a == 14 }
    puts "\n\nMultiplication\n"
    print test.pairs_with_match { |a,b| a * b == 33 }
    puts "\n\nDivison\n"
    print test.pairs_with_match { |a,b| b.to_f / a.to_f == 13 }

  6. arturasl said

    My first Prolog program :)

    s([X1 | _], [X2 | _], C, X1, X2) :- C is X1 + X2.
    s([X1 | T1], [_ | T2], C, A, B) :- s([X1 | T1], T2, C, A, B).
    s([_ | T1], [_ | T2], C, A, B) :- s(T1, T2, C, A, B).
    s([X1 | T1], C, A, B) :- s([X1 | T1], T1, C, A, B).
    
  7. My first program on Haskell


    module Main where

    import System
    import Data.List

    {-
    Write a program that takes a list of integers and a target number and determines if any two integers in the list sum to the target number. If so, return the two numbers.
    If not, return an indication that no such integers exist.
    -}

    main = do

    (sNumber:sList) print "Nothing found"
    Just (x, pair) -> print $ "Yes, there's such an integer: " ++ (show pair)

    where

    determineIntegers :: Integer -> [Integer] -> Maybe (Integer, [Integer])
    determineIntegers number list =

    find (\(x, pair) -> number == x) $ sumPairs pairs

    where

    pairs = filter (\x -> length(x) == 2) $ subsequences list
    sumPairs :: [[Integer]] -> [(Integer, [Integer])]
    sumPairs pairs = map (\x -> (head(x) + last(x), x)) pairs

  8. Bryce said

    I figured that instead of adding two numbers “n” number of times. I could do 1 subtraction, and see if the remainder was in the list. Not sure how good of a solution this is, but it does seem to work.

    import Data.List
    import Data.Maybe

    sumCheck :: Int -> [Int] -> [Int] -> Maybe (Int, Int)
    sumCheck _ [] _ = Nothing
    sumCheck total (x:xs) ys = if total’ == Nothing
    then sumCheck total xs ys
    else return (x, (ys !! ( fromJust total’)))
    where total’ = (total – x) `elemIndex` ys

  9. Brice said

    Clojure FTW!

    (defn sum-two [n xs] 
        (first (for [x xs y xs :when (= n (+ x y))] 
            (list x y))))
    
  10. Aaron said

    %Erlang, the O(n) solution

    -module(my_module).
    -export([twosum/2]).

    twosum( Xs, Target) ->
    twosum( Xs, Target, dict:new() ).

    twosum( Xs, Target, Dict ) ->
    case Xs of
    [] ->
    no_sum;
    _ ->
    [ X | Tail ] = Xs,
    Diff = Target-X,
    case dict:is_key( Diff, Dict ) of
    true ->
    { Diff, X };
    false ->
    twosum( Tail, Target, dict:store( X, X, Dict ) )
    end
    end.

  11. In JavaScript with node.js:


    /**
    * Program that takes a list of integers and a target number and determines if
    * any two integers in the list sum to the target number. If so, return the two
    * numbers. If not, return an indication that no such integers exist.
    *
    * @see http://programmingpraxis.com/2011/07/19/sum-of-two-integers/
    */
    var App = function() {

    /**
    * Determines if any two integer in a given list sum to the target number.
    * @param list A list of integers.
    * @param target The target number.
    */
    this.sum = function(list, target) {

    // Validate input.
    if (list == null || target == null) {
    throw 'Illegal arguments';
    }

    if (list.length == null || list.length < 2) {
    throw 'Illegal arguments';
    }

    var num1, num2;

    for (var i = 0; i < list.length; i++) {
    for (var j = 0; j < list.length; j++) {
    if (list[i] + list[j] == target && i != j) {
    num1 = list[i];
    num2 = list[j];
    break;
    }
    }
    if (num1 != null && num2 != null) {
    break;
    }
    }

    var results = [];

    if (num1 != null && num2 != null) {
    results = [num1, num2];
    }

    return results;
    };
    };

    var list = [1,2,3,4,5,6,7,8,9];
    var target = 18;
    var a = new App();
    var result = a.sum(list, target);

    console.log(result);

  12. James said

    in JS it seems to work but some of the other solutions seem a lot longer than mine, am i doing something wrong? :)

    for(a = 0; a < numbers.length; a++)
    {
    for(b = 0; b < numbers.length; b++)
    {
    if(numbers[a] + numbers[b] == value)
    {
    if((a == b))
    {
    }
    else
    {
    resulta = numbers[a];
    resultb = numbers[b];
    resulttest = true;
    document.write(resulta + " + " + resultb + " = " + value + " “);
    }
    }
    }
    }
    if(!resultTest)
    {
    document.write(“No results”);
    }

  13. James said

    forgot to include teh variables and array

    var numbers=[1,2,3,4,5,6,7,8,9,10,11,12];
    var value = 15;
    var resultTest = false;
    var resulta,resultb;

    for(a = 0; a < numbers.length; a++)
    {
    for(b = 0; b < numbers.length; b++)
    {
    if(numbers[a] + numbers[b] == value)
    {
    if((a == b))
    {
    }
    else
    {
    resulta = numbers[a];
    resultb = numbers[b];
    resulttest = true;
    document.write(resulta + " + " + resultb + " = " + value + " “);
    }
    }
    }
    }
    if(!resultTest)
    {
    document.write(“No results”);
    }

  14. [...] try it out with a miniproject, perhaps from Programming Praxis. I went over there and found the Sum of Two Integers problem, which looked interesting. The problem is given a list of integers and a target integer [...]

  15. My solution in Haskell:

    import Data.List(find)

    findSum :: Num a => a -> [a] -> Bool
    findSum s ns = find (sumIs s) (pairs ns)
    where
    sumIs :: Num a => a -> (a, a) -> Bool
    sumIs s (x, y) = x+y == s

    pairs :: [a] -> [(a, a)]
    pairs xs = pairs’ xs xs

    pairs’ :: [a] -> [a] -> [(a, a)]
    pairs’ [] _ = []
    pairs’ (x:xs) (y:ys) = map (\y->(x,y)) ys ++ pairs’ xs ys

  16. Joseph said

    #!/usr/bin/env python

    import sys
    from itertools import permutations

    def sum_of_ints(ints):
    ints_list = list(ints)
    perms = list(permutations(ints_list, 2))
    list_new = []
    for perm in perms:
    answer = int(perm[0]) + int(perm[1])
    list_new.append(list((perm[0], perm[1], answer)))
    return list_new

    def match_target(list_new, target):
    for l in list_new:
    if l[2] != int(target):
    pass
    else:
    #In the brief we can return when we have a match no need to carry on
    return “hey look %s + %s match your target(%s)” % (l[0], l[1], target)
    return “Sorry no matches :-(”

    list_of_ints = sum_of_ints(sys.argv[1])
    print match_target(list_of_ints, sys.argv[2])

  17. Joseph said

    Ok that makes no sense without formatting

    import sys
    from itertools import permutations
    
    def sum_of_ints(ints):
        ints_list = list(ints)
        perms = list(permutations(ints_list, 2))
        list_new = []
        for perm in perms:
            answer = int(perm[0]) + int(perm[1])
            list_new.append(list((perm[0], perm[1], answer)))
        return list_new
    
    
    def match_target(list_new, target):
        for l in list_new:
            if l[2] != int(target):
                pass
            else:
                #In the brief we can return when we have a match no need to carry on
                return "hey look %s + %s match your target(%s)" % (l[0], l[1], target)
        return "Sorry no matches :-("
            
    list_of_ints = sum_of_ints(sys.argv[1])
    print match_target(list_of_ints, sys.argv[2])
    
  18. anon said


    sumoftwo(List,Sum,X,Y) :- member(X,List), member(Y, List), Sum is X + Y.

  19. @anon:
    As I understand it, you’re not allowed to use the same number twice (unless it’s actually in the list twice). Your code might take the same number twice.

  20. anon said

    @Per Persson – ouch! that’s what comes of trying to be clever. Revised version:


    sumoftwo(List,Sum,X,Y) :- select(X,List,Rest), member(Y,Rest), Sum is X + Y.

  21. CyberSpace17 said

    http://codepad.org/xgnHVxd6

    my C++ version
    it’s got a lot of extra code in it because i wasn’t satisfied with the efficiency of my first attempt
    the only functions relating to the program are findPair() and/or SortFindPair().
    I’m a beginner programmer. Constructive criticism and questions are wanted.

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 616 other followers

%d bloggers like this: