CODEWITHSUNDEEP
pythonalgorithm
godzilla
godzilla

Reputation: 3125

most efficient way to find a sum of two numbers

I am looking into a problem: given an arbitrary list, in this case it is [9,15,1,4,2,3,6], find any two numbers that would sum to a given result (in this case 10). What would be the most efficient way to do this? My solution is n2 in terms of big O notation and even though I have filtered and sorted the numbers I am sure there is a way to do this more efficiently. Thanks in advance

myList  = [9,15,1,4,2,3,6]
myList.sort()
result = 10
myList = filter(lambda x:x < result,myList)
total = 0
for i in myList:
    total = total + 1
    for j in myList[total:]:
        if i + j == result:
            print i,j
            break

Upvotes: 1

Views: 381

Answers (3)

godzilla
godzilla

Reputation: 3125

I think, this solution would work....

list  = [9,15,1,4,2,3,6]
result = 10
list.sort()
list = filter(lambda x:x < result,list)
myMap = {}

for i in list:
    if i in myMap:
        print myMap[i], i
        break
    myMap[result - i] = i

Upvotes: 0

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 250931

Use a dictionary for this and for each item in list look for total_required - item in the dictionary. I have used collections.Counter here because a set can fail if total_required - item is equal to the current item from the list. Overall complexity is O(N):

>>> from collections import Counter
>>> def find_nums(total, seq):
    c = Counter(seq)
    for x in seq:
        rem = total - x
        if rem in c:
            if rem == x and c[rem] > 1:
                return x, rem
            elif rem != x:
                return x, rem
...         
>>> find_nums(2, [1, 1])
(1, 1)
>>> find_nums(2, [1])
>>> find_nums(24, [9,15,1,4,2,3,6])
(9, 15)
>>> find_nums(9, [9,15,1,4,2,3,6])
(3, 6)

Upvotes: 1

IVlad
IVlad

Reputation: 43477

O(n log n) solution

Sort your list. For each number x, binary search for S - x in the list.

O(n) solution

For each number x, see if you have S - x in a hash table. Add x to the hash table.

Note that, if your numbers are really small, the hash table can be a simple array where h[i] = true if i exists in the hash table and false otherwise.

Upvotes: 3

Related Questions