Find All Numbers In A Integer List That Add Up To A Number
I was asked this question on an interview. Given the following list: [1,2,5,7,3,10,13] Find the numbers that add up to 5. My solution was the following: #sort the list: l.sort()
Solution 1:
This will return all elements of the powerset of the input that sum up to 5:
>>>input = [1,2,5,7,3,10,13]>>>import itertools>>>defpowerset(l):...return itertools.chain.from_iterable((itertools.combinations(l, i) for i inrange(len(l)+1)))...>>>filter(lambda v: sum(v) == 5, powerset(input))
[(5,), (2, 3)]
Solution 2:
another solution using dictionaries
from collections import Counter
l = [1,2,2,5,7,3,10,0,-5]
counter = Counter(l)
keys = counter.keys()
result = []
key = keys.pop()
whileTrue:
if5-key in counter:
result.append((key, 5-key))
counter[key]-=1if counter[key]<=0:
del counter[key]
iflen(keys) == 0:
break
key = keys.pop()
counter[5-key]-=1if counter[5-key]<=0:
del counter[5-key]
else:
del counter[key]
iflen(keys) == 0:
break
key = keys.pop()
print(result)
you get
[(-5, 10), (5, 0), (3, 2)]
with
len(l)==1000
timeit for proposal solutions:
from timeit import Timer
t = Timer(jose)
print t.timeit(number=1)
#0.00108003616333
t = Timer(dan)
print t.timeit(number=1)
#hangout
t = Timer(morgan)
print t.timeit(number=1)
#0.000875949859619 <--- best time
t = Timer(steven)
print t.timeit(number=1)
#0.0118129253387
t = Timer(sam) #OPprint t.timeit(number=1)
#0.0160880088806
Solution 3:
This is how I would do it:
from itertools import permutations
from random import randint
base_list = [randint(-10, 10) for x inrange(20)]
deffive_sum(base_list, combinations):
has_negatives = any([base for base in base_list if base < 0])
ifnot has_negatives:
filtered_list = [base for base in base_list if base <= 5]
else:
filtered_list = base_list
perms = list(permutations(filtered_list, combinations))
filtered_perms = [perm for perm in perms ifsum(perm) == 5]
print(filtered_perms)
for perm inset(filtered_perms):
yield perm
print(base_list)
print(list(five_sum(base_list, 2)))
In an ideal world where I had unlimited Memory, I would replace the combinations
parameter with perms = [list(permutations(filtered_list, i)) for i in range(len(filtered_list) + 1)]
Post a Comment for "Find All Numbers In A Integer List That Add Up To A Number"