CODEWITHSUNDEEP
python-3.xlistfor-loopif-statement
cauliflower
cauliflower

Reputation: 41

Function that fills in missing numbers to create complete sequence

I'm trying to create a function that will fill in any missing numbers in between two numbers in a list. The original list must be altered and cannot be new.

For example: [13,15,20] would return [13,14,15,16,17,18,19,20].

Note that I am not allowed to use a range function.

Here's my code:

def complete(list1):
    i= 0
    if len(list1) > 1:
        for number in list1:
           if number - list1[i+1] != -1:
               number += 1
               list1.insert(i + 1, number)
           i += 1
        return list1
    else:
        return list1

I got a "list index out of range" error.

Upvotes: 1

Views: 1198

Answers (2)

Eli Korvigo
Eli Korvigo

Reputation: 10503

Here is the source of your error:

...
for number in list1:
    if number - list1[i+1] != -1:
        ...
    i += 1

Basically, there comes a point (that point being the last number in list1) when i+1 gets you out of bounds and you are not doing anything to prevent that from happening. Indexing is tricky like that, so I would like to offer an indexing-free (well, almost) approach. By the way, from your comment to Bonfire's answer, I see that the task is to change original lists in-place. While mutating arguments is considered a very poor coding practice these days, here is a relatively efficient way of doing that:

import typing as t

def complete_sequence(partial: t.List[int]) -> t.List[int]:
    # edge case
    if len(partial) < 2:
        return partial
    # a lookup table for numbers we already have
    observed = set(partial)
    # append numbers we don't have
    start = partial[0]
    stop = partial[-1]
    num = start + 1
    while num < stop:
        if not num in observed:
            partial.append(num)
        num += 1
    # in-place sort
    partial.sort()
    return partial

As you see, instead of inserting values between existing numbers (paying O(n) time for each insertion), we can simply append everything (O(1) per insertion) and sort. This not only simplifies the logic (we no longer have to track those pesky indices), but also reduces computational time-complexity from O(n^2) to O(n*log(n)).

Upvotes: 2

Diogenis Siganos
Diogenis Siganos

Reputation: 797

To achieve what you want to do I have made some changes to the logic:

def complete(list1):
    if len(list1) < 2 : return list1

    num = list1[0]
    i = -1

    while num < list1[-1]:
        num += 1
        i += 1

        if num in list1: continue

        if i < len(list1) - 1:
            list1.insert(i + 1, num)
        else:
            list1.append(num)

    return list1

print(complete([13, 14, 20]))
#  [13, 14, 15, 16, 17, 18, 19, 20]

print(complete([13, 14, 15]))
#  [13, 14, 15]

Upvotes: 1

Related Questions