Finding a pair of values which add up to given sum

Question

lst = [3, 4, 1, 2, 9]

givenSum = 12
table = {}
x = 0
y = 0

for i in range(0, len(lst)):
    table[givenSum - lst[i]] = 1
    i += 1

for x in table:
    for y in table:
        if (x + y) == givenSum:
            print(x, "and", y, "is equal to", givenSum)
            break

This is the output

9 and 3 is equal to 12
3 and 9 is equal to 12

I don't know why it's being shown up twice. I need to find a pair of values that add up to the given sum and this is the only way I could think of. I only want it to show up once though any ideas on how I can do that?

Use `break` to not output more than one. (You're also uselessly checking the reverse; `break` will help, but it will be slower than it needs to be.) — Amadan, Feb 28 '20 at 06:23
To solve your duplication problem just add `if (x + y) == givenSum: break` to the outer loop — Nick, Feb 28 '20 at 06:30

score 2 · Answer 1 · answered Feb 28 '20 at 06:34

2

There are better solutions, but to fix your issue making minimal changes to your code:

lst = [3, 4, 1, 2, 9]
givenSum = 12

for x in range(0, len(lst) - 1):
    for y in range(x + 1, len(lst)):
        if lst[x] + lst[y] == givenSum:
            print(lst[x], "and", lst[y], "is equal to", givenSum)
            break

This will print

3 and 9 is equal to 12

Note that the redundant table is completely removed from the code.

If you run it for a better test case:

lst = [3, 4, 5, 6, 7, 1, 2, 9]

it will print

3 and 9 is equal to 12
5 and 7 is equal to 12

answered Feb 28 '20 at 06:34

Selcuk

57,004
12
102
110

Doing it this way also has the advantage of not saying `6 and 6 is equal to 12` if there's one `6` in `lst`. – Nick Feb 28 '20 at 06:37
@Nick Exactly. I have specifically included `6` in the second test list. – Selcuk Feb 28 '20 at 06:38

score 1 · Answer 2 · answered Feb 28 '20 at 06:47

First, to address why the looping continues and gives a second output, break can only break out of its immediate loop. Since you have a nested loop, the break only stops the for y in table: inner loop, but allows for x in table outer loop to move onto it's next iteration. So eventually, x is able to take the value of 3 later on, thus giving you the two outputs you see.

So, if you need a way to stop the iteration entirely when a solution is found, you need to either chain the break statements using a for else syntax (which arguably might be tough to read) as follows,

for x in table:
    for y in table:
        if (x + y) == givenSum:
            print(x, "and", y, "is equal to", givenSum)
            break #breaks from inner loop
    else: #for else syntax: this block runs if and only if there was no break encountered during looping.
        continue #jumps the outer loop to next iteration
    break #this break is set at outer loop's level. Essentially, we can only reach this portion if there is a break in the inner loop.

For else says: run through the whole iteration, and if no break is found, executes the code in the else block. Essentially, the "else" of a "for else" is like a "for - no break".

However, one easier alternative is to use a function with a return (which also makes it easier to read the code).

def find_given_sum(lst, givenSum):
    table = {}
    x = 0
    y = 0

    for i in range(0, len(lst)):
        table[givenSum - lst[i]] = 1
        i += 1

    for x in table:
        for y in table:
            if (x + y) == givenSum:
                print(x, "and", y, "is equal to", givenSum)
                return #this returns immediately out of the function, thus stopping the iteration.

Also, you could just repeat the break condition, but repeating code is generally not a good practice.

Hope this helps address why the two outputs are being printed. Now, as for the solution itself, there's actually a much better way to solve this. It builds upon the idea of compliments, which you seem to have a sense of in your table. But it doesn't require iteration over the table itself. As a hint: the ideal solution runs in O(n) time. I will not discuss the ideal solution, but hope this prompts you to find the best approach.

You don't need `table` at all, but for the sake of argument, why don't you pass `table` to the function instead? Note that both methods will fail if there is an element in `lst` which is equal to half of the `givenSum`. — Selcuk, Feb 28 '20 at 06:59
@Selcuk Because i made a conscious decision to focus on the "why" of the observed behaviour for OP's benefit, instead of just handing out the best answer. (edit: i also consider correcting the edge case in part of this bucket. Decided not to focus on it). As for why i didn't pass table to the function, it's simply because that logic is part of OP's solution, and so it really should be bundled with the existing function imo. — Paritosh Singh, Feb 28 '20 at 07:07
tl;dr, I wanted to address why the OP was seeing the behaviour they were seeing, that is all. — Paritosh Singh, Feb 28 '20 at 07:10

score 0 · Answer 3 · answered Feb 28 '20 at 06:40

0

Use itertools to get the result

import itertools
sum = 10
lst = [3, 4, 1, 2, 9]
ans = list(filter(lambda x : x[0]+x[1] == sum,itertools.combinations(lst, 2)))

answered Feb 28 '20 at 06:40

Deepak Tripathi

3,175
1
8
21

score 0 · Accepted Answer · answered Feb 28 '20 at 07:09

Looping twice for n elements costs you O(N^2) time, which is inefficient for large lists. Modified and tested the code to use hash map/dictionary to store the list elements and now it will take only O(N) time.

Map = dict()
lst = [3, 4, 1, 2, 9]
givenSum = 12

for i in range(0, len(lst)):
    rem=givenSum-lst[i]
    if rem in Map:
        print lst[i],lst[Map[rem]]
    else:
        Map[lst[i]]=i

Store the value of each list element into the map whenever it does not exist in the map.
At each iteration, take the difference between givenSum and current element at that iteration and then search for that difference in the Map.
If it exists it means the pair exists or else not.

In this approach you are running the loop only once, which takes O(N) time because accessing elements in hash map is O(1)/constant time.

Finding a pair of values which add up to given sum

4 Answers4