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

Ruby versions (plus simple test cases) …

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.

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 }

A quick scala solution:

def findSums = (a:List[Int], b:List[Int], c:Int) => a.zip(b).filter(v => v._1 + v._2 == c

My first Prolog program :)

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

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

Clojure FTW!

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

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

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

}

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

}

[...] 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 [...]

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

#!/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])

Ok that makes no sense without formatting

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

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

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

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.