## Sum Of Two Integers

### July 19, 2011

We’ll look at three solutions of decreasing time complexity. The first solution is the simple brute-force solution of summing all possible pairs, and runs in time O(n2), where n is the length of the list of integers:

```(define (twosum1 xs t)   (let i-loop ((i 0))     (if (= i (vector-length xs)) #f       (let j-loop ((j (+ i 1)))         (cond ((= j (vector-length xs)) (i-loop (+ i 1)))               ((= (+ (vector-ref xs i) (vector-ref xs j)) t)                 (values (vector-ref xs i) (vector-ref xs j)))               (else (j-loop (+ j 1))))))))```

The second solution has time complexity O(n log n); it sorts the array, then scans one pointer from left to right and another from right to left, testing the sum at each step, increasing the left pointer if the sum is too low, decreasing the right pointer if the sum is too high, and reporting failure if the pointers meet:

```(define (twosum2 xs t)   (vector-sort! xs cmp)   (let loop ((lo 0) (hi (- (vector-length xs) 1)))     (cond ((= lo hi) #f)           ((< (+ (vector-ref xs lo) (vector-ref xs hi)) t) (loop (+ lo 1) hi))           ((< t (+ (vector-ref xs lo) (vector-ref xs hi))) (loop lo (- hi 1)))           (else (values (vector-ref xs lo) (vector-ref xs hi)))))) ```

The third solution uses a hash table and has a time complexity of O(n). Each member of the array is visited once. If the difference between the target value and the current array element is a member of the hash table, then the current array element and the difference are returned. Otherwise, the current array element is inserted into the hash table and the next element of the array is visited. Iteration stops with failure if the array is exhausted:

```(define (twosum3 xs t)   (let ((hash (make-hash (lambda (x) x) = #f 997)))     (let loop ((i 0))       (if (= i (vector-length xs)) #f         (let* ((x (vector-ref xs i)) (t-x (- t x)))             (if (hash 'lookup t-x) (values x t-x)               (begin (hash 'insert x x) (loop (+ i 1)))))))))```

We used hash tables and the vector sort from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/OVsIhFYl.

Pages: 1 2

### 23 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:
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 […]

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

 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 [] = [] pairs' (x:xs) = map (\y->(x,y)) xs ++ pairs xs

view raw

findSum.hs

hosted with ❤ by GitHub

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