IndexError in implementation of Two Sum problem

Question

I write an algorithm that sums up two numbers in a list so that it is equal to 15 or 13 or 7 then deletes those numbers from the original list and then repeats the process. Until there are no more or fewer numbers in the starting list. There is always the following problem: IndexError: list assignment index out of range.

I tried using dictionaries or finding another algorithm, because what I'm doing is a bit of brute force. But in vain.

number = [10,5,14,1,12,2,7,6,10,3,8]
case1=15
case2=13

lc1i = []
lc1j = []
lc2i = []
lc2j = []

def seperate(number,case1,case2):

    for i in number:
        for j in number:
            if i+j == case1:
                lc1i.append(i)
                del number[i]
                lc1j.append(j)
                del number[j]


            elif i+j == case2:
                lc2i.append(i)
                del number[i]
                lc2j.append(j)
                del number[j]
    print(number)

seperate(number,case1,case2)

I expect at the end to have two differents dictionaries: the first one has all pairs which together make 15 and the other all pairs which make 13. but I have this message :IndexError: list assignment index out of range

you are modifying number while iterating it with a for loop. See https://stackoverflow.com/questions/1207406/how-to-remove-items-from-a-list-while-iterating — Kenny Ostrom, Jun 14 '19 at 14:42
What @KennyOstrom says + You speak of dictionaries but are using lists only? — Wimanicesir, Jun 14 '19 at 14:43
Every time you delete numbers from your list, it becomes smaller. At some point its length will be less than `i` in the for loop, so get the error. Also `for i in number` loops through the list elements and not their indices, so any big numbers in the list would also give the same error. — Adarsh Chavakula, Jun 14 '19 at 14:45
While there is an error in how you are iterating and deleting (already commented on), there is also a better way. Research "two sum" — Kenny Ostrom, Jun 14 '19 at 14:47
You only need `O(n log n)` instead of `O(n^2)` if you sort the list? — Neil, Jun 14 '19 at 19:11

score 1 · Accepted Answer · answered Jun 14 '19 at 14:53

A lot of good stuffs have already been pointed out in the comments, just want to add couple of things. If you want to stick to what you are doing currently, what you can do is maintain a list of already processed indexes and rather than deleting items directly from the original list, just check whether or not current index is already processed (by doing an item in list). Something like this:

number = [10,5,14,1,12,2,7,6,10,3,8]
case1=15
case2=13

lc1i = []
lc1j = []
lc2i = []
lc2j = []

# we will store processed indexes to make sure they are not processed again
already_processed_indexes = []

def seperate(number,case1,case2):

    for idx1, i in enumerate(number):
        for idx2, j in enumerate(number):

            # check if indexes are already processed
            if idx1 in already_processed_indexes or idx2 in already_processed_indexes:
              continue

            if i+j == case1:
                lc1i.append(i)
                already_processed_indexes.append(idx1)
                lc1j.append(j)
                already_processed_indexes.append(idx2)


            elif i+j == case2:
                lc2i.append(i)
                already_processed_indexes.append(idx1)
                lc2j.append(j)
                already_processed_indexes.append(idx2)
    print(number)

seperate(number,case1,case2)

score 1 · Answer 2 · answered Jun 14 '19 at 15:06

1

Don't work with list if the order is not important, use sets instead!

number = [10,5,14,1,12,2,7,6,10,3,8]
case1=15
case2=13

result1 = {0}
result2 = {0}

def seperate(number,case1,case2):

    for i in number:
        for j in number:
            if i+j == case1:
                result1.add(i)
            elif i+j == case2:
                result2.add(i)
    print(result1)
    print(result2)


seperate(number,case1,case2)

answered Jun 14 '19 at 15:06

Wimanicesir

4,606
2
11
30

1

What is the advantage of sets above lists? And note that a set also removes duplicates. The question does not state if the input can contain duplicates or not. – wovano Jun 14 '19 at 16:02

wovano · Answer 3 · 2019-06-14T17:08:21.810

There are already a few answers (even an accepted one), but none of them seem to consider the requirement stated in the question:

I expect at the end to have two different dictionaries: the first one has all pairs which together make 15 and the other all pairs which make 13.

(NB: I assume that "lists" are meant instead of "dictionaries" since a dictionary does not make sense in this case, and the example code also works with lists.)

Furthermore, I assume that the same number cannot be used twice. For the given example cases this does not matter, since 15, 13 and 7 are odd, and adding an integer number to itself cannot result in an odd number. However, in the generic case this could matter.

Below is my solution, which

...can handle an arbitrary number of cases, e.g. "15 or 13 or 7" as stated in the question. The function accepts a list of cases instead of exactly two cases.
...returns a list of index pairs for each case (so the return value is a list of lists of tuples of indices, but that sounds worse than it is...)
...is updated to solve a number of pylint warnings and to conform to the PEP8 style guide. It also prints the results for demonstration purposes.

Disclaimer: it's not completely clear to me if all numbers can only be used once, or for all cases. So if 10 and 5 is a pair that sums up to 15, is 10 and 3 then also a valid pair to make 13, or can the 10 only be used once? If I have misunderstood the problem please let me know, so that I can update the code.

Code

NUMBERS = [10, 5, 14, 1, 12, 2, 7, 6, 10, 3, 8]
CASES = [15, 13, 7]


def separate(numbers, cases):
    results = []
    for case in cases:
        result = []
        remaining_indices = list(range(len(numbers)))
        while remaining_indices:
            i = remaining_indices.pop(0)
            for j in remaining_indices:
                if numbers[i] + numbers[j] == case:
                    result.append((i, j))
                    remaining_indices.remove(j)
                    break
        results.append(result)
    return results


def main():
    case_results = separate(NUMBERS, CASES)

    # PRINT THE RESULTS:
    for idx, case in enumerate(CASES):
        for i, j in case_results[idx]:
            print('%2d + %2d = %2d' % (NUMBERS[i], NUMBERS[j], case))
        print('')

if __name__ == '__main__':
    main()

Output

10 +  5 = 15
14 +  1 = 15
12 +  3 = 15
 7 +  8 = 15

10 +  3 = 13
 5 +  8 = 13
 1 + 12 = 13
 7 +  6 = 13

 5 +  2 =  7
 1 +  6 =  7

IndexError in implementation of Two Sum problem

3 Answers3