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.

Pages: 1 2

22 Responses to “Sum Of Two Integers”

1. Graham said
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:
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, 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 }

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 https://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)
{
}

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

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) + int(perm)
return list_new

def match_target(list_new, target):
for l in list_new:
if l != 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, l, target)
return “Sorry no matches :-(”

list_of_ints = sum_of_ints(sys.argv)
print match_target(list_of_ints, sys.argv)

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) + int(perm)
return list_new

def match_target(list_new, target):
for l in list_new:
if l != 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, l, target)
return "Sorry no matches :-("

list_of_ints = sum_of_ints(sys.argv)
print match_target(list_of_ints, sys.argv)

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