CODEWITHSUNDEEP
pythonlistsorting
Sam Hammamy
Sam Hammamy

Reputation: 11017

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()
result = ()
for i in range(len(l)):
    for j in range(i, len(l)):
         if l[i] + l[j] > 5:
             break
         elif l[i] + l[j] == 5:
             result += (l[i], l[j])

The idea I presented was to sort the list, then loop and see if the sum is greater than 5. If so, then I can stop the loop. I got the sense the interviewer was dissatisfied with this answer. Can someone suggest a better one for my future reference?

Upvotes: 3

Views: 1289

Answers (3)

Morgan Thrapp
Morgan Thrapp

Reputation: 9986

This is how I would do it:

from itertools import permutations
from random import randint


base_list = [randint(-10, 10) for x in range(20)]

def five_sum(base_list, combinations):
    has_negatives = any([base for base in base_list if base < 0])
    if not 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 if sum(perm) == 5]
    print(filtered_perms)
    for perm in set(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)]

Upvotes: 2

Jose Ricardo Bustos M.
Jose Ricardo Bustos M.

Reputation: 8174

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()

while True:
  if 5-key in counter:
    result.append((key, 5-key))
    counter[key]-=1
    if counter[key]<=0:
      del counter[key]
      if len(keys) == 0:
        break
      key = keys.pop()
    counter[5-key]-=1
    if counter[5-key]<=0:
      del counter[5-key]
  else:
    del counter[key]        
    if len(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) #OP
print t.timeit(number=1)
#0.0160880088806

Upvotes: 2

Dan D.
Dan D.

Reputation: 74655

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
>>> def powerset(l):
...     return itertools.chain.from_iterable((itertools.combinations(l, i) for i in range(len(l)+1)))
...
>>> filter(lambda v: sum(v) == 5, powerset(input))
[(5,), (2, 3)]

Upvotes: 4

Related Questions