2
\$\begingroup\$

Given there's a list of random number and the amount I want to find.

For example:

[80, 98, 83, 92, 1, 38, 37, 54, 58, 89]

And I want two numbers that add up to a given total in this case it's 181. So, it's going to be (92+89). The list could be really big.

Here's the solution I come up with. But it's kinds brute force and I was wondering if there's a better way of doing this.

for i, item in enumerate(numbers):
    for j in range(i+1, len(numbers)):
        total_of_two_items = numbers[i] + numbers[j]
        if(total_of_two_items == total_number):
            print '{first_item} {second_item}'.format(first_item=i+1, second_item=j+1)
            print '\n'
\$\endgroup\$
  • 2
    \$\begingroup\$ Sort the numbers in ascending order (for example) and then iteratively compare the head and tail of the resulting list. There are only three options: The head is too small, the tail is too big, or they are just right ;-) \$\endgroup\$ – twohundredping Jun 15 '15 at 18:34
  • \$\begingroup\$ Agree with @twohundredping Also for any given number, you know what its pair would have to be, so you might check if performance is better to search for a specific number int he ordered list. Also once you have chosen a number, you don't have to search the entire list for its pair. Also a pair is the same whether you choose the lower or higher number first, so even for the top for loop, you should probably only search half of an ordered list. \$\endgroup\$ – sunny Jun 16 '15 at 16:18
1
\$\begingroup\$

Here is an alternative approach using set logic, which is O(n) in the average case:

n = 181
n2 = n//2
numbers = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
goodnums = {n-x for x in numbers if x<=n2} & {x for x in numbers if x>n2}
pairs = {(n-x, x) for x in goodnums}

What this does is first filter out values that are greater than 1/2 the target value, since one number in each pair must be that way. Then it subtracts the remaining numbers from the target (in this case 181). This gets the other value from the pair. Then it uses set logic to extract only those values where the other value is present in the original list of numbers.

So to put it more briefly, it finds all values x such that 181-x is also present in the list.

Edit: If you don't want to include cases where both members of the pair are equal and it only exists once, such as n=2 and numbers = [1], as Gareth pointed out, add this to the end:

if not n%2 and (n2, n2) in pairs and numbers.count(n2) == 1:
   pairs.remove((n2, n2))

This will check if n is even and, if so, if there is exactly one value where x==n//2, if so remove (n//2, n//2) from the results.

\$\endgroup\$
  • \$\begingroup\$ This goes wrong in the case n = 2 and numbers = [1]. \$\endgroup\$ – Gareth Rees Jun 15 '15 at 19:17
  • \$\begingroup\$ It returns [(1,1)]. Is this not the expect value in such a case? \$\endgroup\$ – TheBlackCat Jun 15 '15 at 19:18
  • \$\begingroup\$ numbers has only one element: it can't possibly contain two numbers that add up to anything. In other words: the items have to be chosen without replacement. See the original post, which is careful only to consider items at different indexes in the list. \$\endgroup\$ – Gareth Rees Jun 15 '15 at 19:25
  • \$\begingroup\$ @GarethRees I added an optional bit of code to handle this case. \$\endgroup\$ – TheBlackCat Jun 15 '15 at 19:33
  • 1
    \$\begingroup\$ @user2023861 I am not using arrays, I am using sets. Yes, for arrays it is O(n*n). But for sets the same operation is O(n). This is because it uses a hash table for value lookups. Looking up a value in an array is a O(n), but looking up a value in a well-structured hash table is O(1) (in CPython, hash tables of integers are always well-structured). Since it is doing a O(1) operation on each element of one of the sets, it is a O(1*n) operation overall, or O(n). You can see this in the official python Time Complexity page. \$\endgroup\$ – TheBlackCat Jun 16 '15 at 13:39
0
\$\begingroup\$

We first sort the list and then keep comparing the ends of the sorted list to get those pairs of numbers which sum to a given number. Merge sort has been used here, however any other sorting algorithm can also be used. The main logic is in the find_pairs function.

def mergeSort(A):

    if len(A) > 1:
        mid = len(A)//2
        lefthalf = A[:mid]
        righthalf = A[mid:]

        mergeSort(lefthalf)
        mergeSort(righthalf)

        # Merge the halves
        i,j,k=0,0,0

        while i<len(lefthalf) and j<len(righthalf):
            if lefthalf[i] < righthalf[j]:
                A[k] = lefthalf[i]
                i = i + 1
            else:
                A[k] = righthalf[j]
                j = j + 1
            k = k + 1

        while i < len(lefthalf):
            A[k] = lefthalf[i]
            k = k +1
            i = i + 1

        while j < len(righthalf):
            A[k] = righthalf[j]
            k = k + 1
            j = j + 1


def find_pairs(alist, item):
    # We take two flags left and right to point to the ends of the sorted list
    left = 0
    right = len(alist) - 1
    pairs = []
    while(left<right):
        # We find the sum of the numbers in at these two points.
        # If the sum is equal to our number for which we are finding pairs, we consider this pair and add it to our results
        # If the sum is greater than expected then we move the right pointer one step back to a smaller number and then compute sum again
        # If the sum is smaller than expected then we move the left pointer a step ahead and check the sum with a greater number
        sum = alist[left] + alist[right]
        if sum == item:
            pairs += [(alist[left],alist[right])]
            # Move the pointers to next elements in the list and find more pairs
            right -= 1
            left += 1
        elif sum > item:
            right -= 1
        else:
            left += 1
    return pairs


l1 = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
mergeSort(l1)
print l1
print find_pairs(l1,181)

l2 = [-5,-2, -23, 34,21,90,1,0,65,8,-10]
mergeSort(l2)
print l2 
print find_pairs(l2,-2)

The output of the above program is:

[1, 37, 38, 54, 58, 80, 83, 89, 92, 98]
[(83, 98), (89, 92)]


[-23, -10, -5, -2, 0, 1, 8, 21, 34, 65, 90]
[(-23, 21), (-10, 8), (-2, 0)]
\$\endgroup\$
  • \$\begingroup\$ This appears to output the values that sum to the target total, rather than the indices of those values as in the original code. \$\endgroup\$ – Toby Speight Oct 25 '18 at 13:38
0
\$\begingroup\$

I came up with the following, which ends up using a dictionary as a helper to avoid the set operations and extra testing:

def sum_of_pairs_matches(K, arr):
    uniques = {i: True for i in arr}
    pairs = set()
    for val in arr:
        k = -val + K if val<K else -K - val
        if(uniques.get(k, False)):
            pairs.add(tuple(sorted([k,val])))
    return pairs

Running:

sum_of_pairs_matches(5, [-5, -4, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])

will yield

{(-5, 10), (-4, 9), (-1, 6), (0, 5), (1, 4), (2, 3)}
\$\endgroup\$
  • \$\begingroup\$ This appears to output the values that sum to the target total, rather than the indices of those values as in the original code. \$\endgroup\$ – Toby Speight Oct 25 '18 at 13:38
0
\$\begingroup\$

It's really worth writing this as a function. That will make it easier to test, and it's an opportunity to give it a sensible name and a docstring describing what it does (it's not obvious from your description that you wanted to output the positions of the found numbers, rather than the numbers themselves):

def find_2sum(target, numbers):
    """Find indexes of pairs from NUMBERS that add to TARGET"""
    for i, item in enumerate(numbers):
        for j in range(i+1, len(numbers)):
            total_of_two_items = numbers[i] + numbers[j]
            if(total_of_two_items == target):
                print('{first_item} {second_item}'.format(first_item=i+1, second_item=j+1))
                print('\n')

if __name__ == '__main__':
    find_2sum(181, [80, 98, 83, 92, 1, 38, 37, 54, 58, 89])

We can improve the interface by returning the index pairs instead of printing them. That pares the function down to its essential responsibility, instead of it finding and printing the results:

def find_2sum(target, numbers):
    """Find indexes of pairs from NUMBERS that add to TARGET"""
    for i, item in enumerate(numbers):
        for j in range(i+1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                yield [i, j]

if __name__ == '__main__':
    for i,j in find_2sum(181, [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]):
        print('{} {}'.format(i+1, j+1))

Now, let's look at the implementation. The first thing that strikes me is that we enumerate numbers, but never use the item we obtain. We might as well have written

for i in range(len(numbers)):

Perhaps we could enumerate() the list once, and use it for both augends:

def find_2sum(target, numbers):
    """Find indexes of pairs from NUMBERS that add to TARGET"""
    numbers = list(enumerate(numbers))
    while numbers:
        i, first = numbers.pop(0)
        for j, second in numbers:
            if first + second == target:
                yield [i, j]

We still have an efficiency problem, in that we're adding every possible pair and testing it against the target sum. We can avoid the addition by using a single subtraction outside the loop, but this still requires looking at all pairs, so still scales as O(n²):

def find_2sum(target, numbers):
    """Find indexes of pairs from NUMBERS that add to TARGET"""
    numbers = list(enumerate(numbers))
    while numbers:
        i, first = numbers.pop(0)
        difference = target - first
        for j, second in numbers:
            if second == difference:
                yield [i, j]

What we really need to do now is to improve our search for difference. We'll need to use an additional data structure that can locate it in sub-linear time. The obvious choice would be a dict that maps from value to index; for a general solution, we'll need it to map to a list of indexes, because any number may appear multiple times. We can build such a map quite easily:

    index_map = collections.defaultdict(list)
    for i, item in enumerate(numbers):
        index_map[item].append(i)

The reading is a bit more involved: once we find two values that sum to the target, we need to form all combinations of the first value's indexes and the second value's indexes, like this:

    for first, indices in index_map.items():
        difference = target - first
        other_indices = index_map.get(difference, [])
        for i in indices:
            for j in other_indices:
                yield [i, j]

If we do this, we'll see that we produce every pair twice, once in each order. We can fix this by ignoring the cases where the first is bigger than the second:

    for first, indices in index_map.items():
        difference = target - first
        if first < difference:
            other_indices = index_map.get(difference, [])
            for i in indices:
                for j in other_indices:
                    yield [i, j]

There's another case we missed, and we can demonstrate with a simple test case:

for i,j in find_2sum((6, [2, 2, 3, 3, 3, 4, 4]):
    print('{} {}'.format(i+1, j+1))

Because 3 is exactly half of 6, we need to enumerate all the combinations of these:

        if first == difference:
            while indices:
                i = indices.pop()
                for j in indices:
                    yield [i, j]

We produce results in somewhat arbitrary order, as we're using an unsorted dict. If we want a consistent order to the results, the best way is to sort them after they are generated:

for i,j in sorted(sorted(x) for x in find_2sum(6, [2, 2, 3, 3, 3, 4, 4])):
    print('{} {}'.format(i+1, j+1))

Full program

import collections

def find_2sum(target, numbers):
    """Find indexes of pairs from NUMBERS that add to TARGET"""
    index_map = collections.defaultdict(list)
    for i, item in enumerate(numbers):
        index_map[item].append(i)

    # now read from index_map
    for first, indices in index_map.items():
        difference = target - first
        if first == difference:
            # return all distinct pairs from indices (we won't need it again)
            while indices:
                i = indices.pop()
                for j in indices:
                    yield [i, j]
        elif first < difference:
            # normal case - return all combinations of first and second
            other_indices = index_map.get(difference, [])
            for i in indices:
                for j in other_indices:
                    yield [i, j]

if __name__ == '__main__':
    for i,j in find_2sum(181, [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]):
        print('{} {}'.format(i+1, j+1))

    print()
    for i,j in sorted(sorted(x) for x in find_2sum(6, [2, 2, 3, 3, 3, 4, 4])):
        print('{} {}'.format(i+1, j+1))
\$\endgroup\$
0
\$\begingroup\$

Its faster to check what your desired total (e.g. 181) minus every Listelement is and then see if the answer is also in the list.

def addup(List, K):
    for index,item in enumerate(List):
        if K - item in List[:index] + List[index+1:]:
            return True
    return False


X = [80, 98, 83, 92, 1, 38, 37, 54, 58, 89]
Y = 181

print addup(X,Y)
\$\endgroup\$
  • 2
    \$\begingroup\$ That sounds identical to the approach presented by TheBlackCat..."So to put it more briefly, it finds all values x such that 181-x is also present in the list." \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Nov 16 '18 at 22:28
  • \$\begingroup\$ Yes, you are right. I didn't check it properly. \$\endgroup\$ – Raini Kandi Nov 17 '18 at 23:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.