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.
Programming Praxis 
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 None""" 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')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)}"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` ysClojure FTW!
(defn sum-two [n xs] (first (for [x xs y xs :when (= n (+ x y))] (list x y))))%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
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.
Learn more about bidirectional Unicode characters
findSum.hs
hosted with ❤ by GitHub
#!/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
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])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 […]