Checking sum of items in a list if equals target value

Question

I am trying to make a program that checks whether which items are equal to a target value in a list and then output their indexes.

E.g.

li = [2, 5, 7, 9, 3]
target = 16

output: [2, 3]

li = [2, 5, 7, 9, 3]
target = 7

output: [0, 1]

`[[i1, i2] for i1, v1 in enumerate(li) for i2, v2 in enumerate(li[i1 + 1:], i1 + 1) if v1 + v2 == 16]` — Olvin Roght, Aug 20 '21 at 17:22

Armaggheddon · Answer 1 · 2021-08-20T21:59:11.507

1

Another way, assuming you can sort the list is the following

original_l = [1,2,6,4,9,3]
my_l = [ [index, item] for item,index in zip(original_l, range(0,len(original_l)))]
my_l_sort = sorted(my_l, key=lambda x: x[1])
start_i = 0
end_i = len(my_l_sort)-1
result = []
target = 7
while start_i < end_i:
    if my_l_sort[start_i][1] + my_l_sort[end_i][1] == target:
        result.append([my_l_sort[start_i][0], my_l_sort[end_i][0]])
        break
    elif my_l_sort[start_i][1] + my_l_sort[end_i][1] < target:
        start_i+=1
    else:
        end_i-=1
        
if len(result) != 0:
    print(f"Match for indices {result[0]}")
else:
    print("No match")

The indices 0 and 1 of result[0] are respectively the 2 positions, given as a 2 element string, in original_l that holds the values that summed give the target.

edited Aug 20 '21 at 21:59

answered Aug 20 '21 at 17:43

Armaggheddon

340
1
10

You're sorting list, which makes impossible to return *original* indexes. – Olvin Roght Aug 20 '21 at 17:54
True, instead of using the list in the code you could use another list that will be a list of lists where each item will be like [global position, value] and call `l = sorted(l, key=lambda x: x[1])` and of course the code needs to be edited to account for the shift in the actual values that needs to be compared. In result then you would have the original index in the first position and the value in the second. As soon as I get home I will edit my answer. Thank you for the hint! – Armaggheddon Aug 20 '21 at 18:30
1

This code will be very, very hard to maintain as-is. – Thorbjørn Ravn Andersen Aug 22 '21 at 21:16
Well, as always it depends if what you are trying to achieve is readability or speed. Sure for such an easy task (and given the size of the set) there is no point in having this much code that can be quite intimidating at first and an easier more readable way could be better, but would still achieve the same result. – Armaggheddon Aug 22 '21 at 21:24

Alaaaaa · Answer 2 · 2021-08-20T17:23:35.487

0

is this a homework?

Anyways, here is the answer you are looking for

def check_sum(l, target):
    for i in range(len(l)):
        sum_temp = 0
        for j in range(i, len(l)):
            if sum_temp == target:
                return [i, j-1]
            else:
                sum_temp += l[j]
    return None


print(check_sum([2, 5, 7, 9, 3], 16))

"""
check_sum([2, 5, 7, 9, 3], 16)
>>> [2, 3]
check_sum([2, 5, 7, 9, 3], 7)
>>> [0, 1]
check_sum([2, 5, 7, 9, 3], 99)
>>> None
"""

The code is self-explanatory and does not require extra commenting. It simply iterates over the list of integers you have as an input and tries to find a sequence of values that add up to your target.

edited Aug 20 '21 at 17:23

answered Aug 20 '21 at 17:19

Alaaaaa

179
6

Thank you so much, this was very helpful, really appreciate it and yes it is part of an Assignment for school. – Awonke Aug 21 '21 at 00:23
@Awonke Sure you wlecome. Please mark this answer as "accepted" if it solves your issue. – Alaaaaa Aug 21 '21 at 16:00

eroot163pi · Answer 3 · 2021-08-20T18:19:26.917

If you dont worry about stack explosion, for smaller input.

We divide solutions containing an index and not containing index and merge all those solution. It returns indices of all possible solutions.

It is O(2^n) solutions. Similar ones

def solve(residual_sum, original_list, present_index):
    '''Returns list of list of indices where sum gives residual_sum'''
    if present_index == len(original_list)-1:
        # If at end of list
        if residual_sum == original_list[-1]:
            # if residual sum if equal to present element
            # then this index is part of solution
            return [[present_index]]
        if residual_sum == 0:
            # 0 sum, empty solution
            return [[]]
        # Reaching here would mean list at caller side can not
        # lead to desired sum, so there is no solution possible
        return []
    all_sols = []
    # Get all solutions which contain i
    # since i is part of solution,
    # so we only need to find for residual_sum-original_list[present_index]
    solutions_with_i = solve(residual_sum-original_list[present_index], original_list, present_index+1)
    if solutions_with_i:
        # Add solutions containing i 
        all_sols.extend([[present_index] + x for x in solutions_with_i])
    # solution dont contain i, so use same residual sum
    solutions_without_i = solve(residual_sum, original_list, present_index+1)
    if solutions_without_i:
        all_sols.extend(solutions_without_i)
    return all_sols

print(solve(16, [2, 5, 7, 9, 3], 0))

Indices

[[0, 1, 3], [2, 3]]

Checking sum of items in a list if equals target value

3 Answers3