CODEWITHSUNDEEP
pythonpython-3.x
sean
sean

Reputation: 11

How to find pair of numbers that sums up to a given value?

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

Upvotes: 1

Views: 3167

Answers (4)

Maciek
Maciek

Reputation: 590

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

Upvotes: 0

Jussi Nurminen
Jussi Nurminen

Reputation: 2408

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)

Upvotes: 2

Ertugrul
Ertugrul

Reputation: 143

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

Upvotes: 1

Henry Tjhia
Henry Tjhia

Reputation: 752

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

Upvotes: 0

Related Questions