July 19, 2011 9:00 AM
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.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
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 NoneBy Graham on July 19, 2011 at 2:31 PM
""" 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')By Mike on July 19, 2011 at 7:47 PM
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)}"By slabounty on July 20, 2011 at 3:23 AM
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.
By Ecodelta on July 21, 2011 at 6:31 AM
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 }
By Stephen Lemp on July 21, 2011 at 3:41 PM
A quick scala solution:
def findSums = (a:List[Int], b:List[Int], c:Int) => a.zip(b).filter(v => v._1 + v._2 == c
By rjf89 on July 23, 2011 at 2:21 AM
My first Prolog program :)
By arturasl on July 24, 2011 at 4:34 PM
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
By Тимурка on July 25, 2011 at 7:28 AM
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` ysBy Bryce on July 26, 2011 at 3:41 AM
Clojure FTW!
(defn sum-two [n xs] (first (for [x xs y xs :when (= n (+ x y))] (list x y))))By Brice on July 27, 2011 at 7:41 PM
%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.
By Aaron on July 29, 2011 at 2:06 AM
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);
By Rubens Mariuzzo on August 3, 2011 at 2:40 AM
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”);
}
By James on August 3, 2011 at 12:38 PM
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”);
}
By James on August 3, 2011 at 12:39 PM
[…] 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 […]
By Sum Of Two Integers | Irreal on August 4, 2011 at 6:14 PM
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
findSum.hs
hosted with ❤ by GitHub
By Per Persson on August 20, 2011 at 6:46 PM
#!/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])
By Joseph on August 20, 2011 at 11:32 PM
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])By Joseph on August 20, 2011 at 11:39 PM
sumoftwo(List,Sum,X,Y) :- member(X,List), member(Y, List), Sum is X + Y.
By anon on August 26, 2011 at 10:36 AM
@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.
By Per Persson on August 26, 2011 at 10:41 AM
@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.
By anon on August 26, 2011 at 5:59 PM
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.
By CyberSpace17 on August 30, 2011 at 4:24 AM
[…] done this in a previous exercise, but it’s a common problem both as an interview question and in programming classes, and […]
By 2SUM | Programming Praxis on March 10, 2020 at 9:01 AM