## 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*(*n*^{2}), 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.

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

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.

[…] done this in a previous exercise, but it’s a common problem both as an interview question and in programming classes, and […]