0

I want to write a function that takes a list of distinct positive integers and a target positive integer value, and then returns a list of the pairs of integers where each pair sums up to the target value.

This is my code but it only shows one pair of numbers:

def pairsum(list1, target):
  for i in range(len(list1) -1):
    for j in range(i + 1 ,len(list1)):
      if list1[i]+ list1[j] == target:
        return (list1[i], list1[j])

pairsum([3,2,6,1,5,4], 7)

When I call pairsum([3,2,6,1,5,4], 7) the output is (3,4) which should be [(1,6), (2,5), (3,4)]. result should be in ascending order of the first element in each tuple. i am not allowed to imporst anything

sean
  • 1
  • 2

4 Answers4

1

Here's a one-liner using itertools:

import itertools

def pairsum(vals, target):
    return sorted([(a, b) for a, b in itertools.combinations(vals, 2) if a + b == target])

Explanation:

  • itertools.combinations(vals, 2) creates all 2-element combinations
  • the 'if' part filters those into combinations that sum to the target
  • the accepted combinations are combined into a list of tuples that is finally sorted (by the first element of each tuple)
Jussi Nurminen
  • 2,257
  • 1
  • 9
  • 16
0
def pairsum(a_list, num):
    pool = a_list.copy()
    first = pool.pop()
    res = []

    while True:
        for second in pool:
            if first + second == num:
                break

        if first < second:
            res.append((first, second))
        else:
            res.append((second, first))

        pool.remove(second)

        if pool:
            first = pool.pop()
        else:
            break

    return sorted(res)

#[(1, 6), (2, 5), (3, 4)]
print(pairsum([3,2,6,1,5,4], 7))
Henry Tjhia
  • 742
  • 1
  • 5
  • 11
  • thank you , is it possible to sort the outputs ? so we get [(1,6), (2,5), (3,4)] instead of [(4, 3), (5, 2), (1, 6)] – sean Dec 11 '20 at 12:55
0

You can try this,

def pairsum(list, target):
    result = []
    loop = 1
    for x in list:
        for y in list:
            if x + y == target:
                result.append((x, y))
        list = list[loop:]
        loop += 1
    return result
Ertugrul Sungur
  • 102
  • 7
  • thank you , is it possible to sort the outputs ? so we get [(1,6), (2,5), (3,4)] instead of [(4, 3), (5, 2), (1, 6)] – sean Dec 11 '20 at 13:05
  • You're welcome! You shouldn't get same outputs because in this code we delete which item we checked. – Ertugrul Sungur Dec 11 '20 at 13:15
  • Your code's problem is that you should keep which items provide your contidion in a list. Then, return command should work when your for loops finished and return list where you keep items. – Ertugrul Sungur Dec 11 '20 at 13:46
0

Your solution was probably designed to use optimized algorithm which complexity is O(n log n) (if you do clever sorting you might get down to O(n) - more information here Is there an O(n) integer sorting algorithm?). The one you proposed (and majority of proposal I have noticed) is O(n^2).

You can try this code, you won't get a better algorithm, but you can still change the logic a bit (storage might be set instead of dict if you are interested only in values, not indicies):

def pairsum(list1, target):
    storage = {}
    output = []
    for i, value in enumerate(list1):
        if value in storage:
            pair = tuple(sorted([value, target-value]))  # you can easily transform it to return indices of elements:
            # pair = tuple(i, storage[value])
            output.append(pair)
            # storage.pop(value)  # consider adding this line in case you want to handle reuses of the same value
        else:
            storage[target-value] = i
    return sorted(output)

Read the comments to adjust it to your needs. Output for given test (pairsum([3,2,6,1,5,4], 7)):
[(1, 6), (2, 5), (3, 4)]

Maciek
  • 463
  • 8
  • 22