How to find a pair of hunted values for a given value with lopps?

Question

I am trying to write a function that gets a list of numbers and an integer and returns a tuple that containing pair of numbers from the list whose sum is the must closest to the number the function received. for example: closest([10,22,28,29,30,40], 54) --> (22,30) It is important for me to do this in loop and in time complexity of O(n). The problem with my code is that the loop does not want to rerun the list end for any value I take from the beginning of the list... I would appreciate help :) Thanks for the helpers!

def closest(lst, x):
    max_num = 0
    cur = lst[0]
    final = 0
    my_tup = ()
    for num in lst[::-1]:
        max_num = cur + num
        if max_num <= x:
            if max_num > final:
                final = max_num
                my_tup = (cur, num)
            else:
                cur = lst[1]

    return my_tup

print(closest([10,22,28,29,30,40], 54))  ---> return: (22,29)

score 1 · Answer 1 · answered Feb 17 '20 at 14:37

The important part that you might not have noticed is that your input list is sorted.

10,22,28,29,30,40

Which means you can take advantage of this information to find the pair you're looking for in a single scan of the list. The intuition is that if you need a larger number, you can go towards the end of the list. These kind of solutions are referred to as the two-pointer technique

The problem you're trying to solve is a variant of the 2SUM problem. There are solutions online such as here

However I would suggest that you read through the first couple of links & try to solve it by yourself.

score 1 · Answer 2 · answered Feb 17 '20 at 14:38

By using the itertools module and a dictionary where the keys are the sums of the pairs and the values are lists of pairs:

from itertools import combinations


def closest(lst, val):
    d = {}
    for element in combinations(lst, 2):
        elem_sum = sum(element)
        try:
            d[elem_sum].append(element)
        except KeyError:
            d[elem_sum] = [element]
    return d[min(d, key=lambda x: abs(x-val))]


>>> closest([10, 22, 28, 29, 30, 40], 54)
[(22, 30)]

score 0 · Answer 3 · answered Feb 17 '20 at 14:31

0

If the list that you give is sorted and the elements are unique you can use this.Otherwise I believe that you can implement some conditions to the dictionary and get the values you want.

my_dict = {i+j:(i,j) for i in mylist for j in mylist if i != j and i + j < bound} my_dict[max(t)]

answered Feb 17 '20 at 14:31

K. Karatopcu

49
3

It this `O(n^2)` ? – quamrana Feb 17 '20 at 14:35
You will end with duplicates such as (22, 30) and (30, 22) – Frodon Feb 17 '20 at 14:59

ALollz · Answer 4 · 2020-02-17T15:56:50.550

Since you require tuples of exactly 2 elements this can be done with numpy to find the pair of points that are closest to x. Do the outer addition of the list with itself, find the closest absolute distance to x.

import numpy as np

def closest(lst, x):
    arr = np.array(lst)
    mat = np.abs(x - (arr[:, None] + arr)).astype(float)
    mat[np.diag_indices_from(mat)] = np.NaN # Exclude tuples of same point with itself 
    i,j = np.unravel_index(np.nanargmin(mat), mat.shape)

    return arr[i], arr[j]

closest([10,22,28,29,30,40], 54)
(22, 30)

closest([10,27,28,29,30,40], 54)
(27, 28)

How to find a pair of hunted values for a given value with lopps?

4 Answers4