Finding missing element from the list

Question

I wrote this code to find a missing positive integer from a given list, but still, it returns None in some cases.

For example, given the array A = [2, 4, 1, 5], the function should return 3, as it is the missing element in the consecutive sequence (1 2 3 4 5).

What am I doing wrong?

def solution(A):
    i = 1
    while i<len(A):
        if i not in A:
            return i
        i += 1

Answer 1

Find missing numbers

Using range(start, stop) we can build a sorted list which already contains all the numbers. Now it's just matter of finding the missing values in your list.

Our range will be made using the lower and higher values of your list. range(min(A), max(A)).

def solution(A):
    missings = []
    for n in range(min(A), max(A)): # Iterate over each number in the sorted and complete list.
        if n not in A: # If that number isn't in your list.
            missings.append(n)
    return missings

Or as a list comprehension in one line:

def solution(A): return [n for n in range(min(A), max(A)) if n not in A]

Example:

>>> solution([1, 9, 4, 3, 11, 5, 7])
[2, 6, 8, 10]

Find non-negative missing numbers

But you said "find a missing positive integer", so you don't want negatives ones.

Just change the min(A) part of range(min(A), max(A)) to range(max(0, min(A)), max(A)).
max(0, min(A)) will use max to give you the bigger number between 0 and your lower actual value, so negative ones are replaced by 0.

Example:

>>> solution([-4, -5, 1, 9])
[0, 2, 3, 4, 5, 6, 7, 8]

Find non-negative missing number after the lower non-negative number

But as said before, you only said: "find a missing positive integer", so at first, I understood you don't want negatives ones.
But, what if you only want the missing (as my first idea) non-negative values (as the second idea) after the lower non-negative value (new idea)?

Easy!
Just change the min(A) part of range(min(A), max(A)) to range(min([n for n in A if n >= 0]), max(A)).
min([n for n in A if n >= 0]) will look for the lower non-negative value in your list.

Example:

>>> solution([-4, -5, 3, 9])
[4, 5, 6, 7, 8]

Answer 2

If you sort the list or approximate a sorted list using the range function, you can make use of a list comprehension:

def solution(A):
    return [value for value in range(min(A),max(A)) if value not in A]

We're basically saying, look at the sequence of numbers beginning with the min value of A to the max value of A, and if any of those values are not in the original A list, return those. This will return multiple missing values, e.g.:

>>> def solution(A):
...     return [value for value in range(min(A),max(A)) if value not in A]
...
A = [1, 2, 3, 4, 7, 8, 10]
>>> solution(A)
[5, 6, 9]
>>>
>>> A = [2, 4, 1, 5]
>>>
>>> solution(A)
[3]

Note: you mentioned "positive" integers, and not sure if that was a strict requirement or not, but this doesn't account for negative values.

I think we can account for that:

def solution(A):
     positive = range(min([max(0,min(A))]),max(A))
     return [value for value in positive if value not in A]

For example:

>>> A = [-6,-8,2,3,5]
>>> solution(A)
[0, 1, 4]

Answer 3

Seems to work fine. Here's an alternative:

def solution(A):
    a = set(A)
    for i, _ in enumerate(A, 1):
        if i in a:
            continue
        return i

solution(A)
# 3

Answer 4

Well, this works the best to find missing element from the list.

def solution(A):
    if len(A) == 0:
        return 1
    return sum(range(1, len(A)+2)) - sum(A)

Answer 5

With the i += 1 inside the loop, there's only an off-by-one error. If A has a length of n, and n is missing from A, but n+1 exist in A, then the function will return None. This can be fixed by looping to len(a)+1.

def solution(A):
    length = len(A) + 1
    i = 1 
    while i < length:
        if i not in A:
            return i
        i += 1

---

By your definition of what a missing-positive integer is, this can be found through some math.

def solution(A):
    n = len(A) + 1
    list_sum = (n * (n+1)) / 2
    a_sum = sum(A)
    missing = list_sum - a_sum
    if missing != n:
        return missing

Take the length of the list and add one and define it as n. Use the equation to sum contiguous positive integers and save it into list_sum. Find the sum of A. The difference of list_sum and a_sum will be the missing integer since we're guaranteed that only one integer can be missing. To keep with the behavior of your function, if the missing number ends to be n, then we know there are no missing numbers, so return None.

Answer 6

You need to be aware that i < len(A) is causing some problem.

Given this example:

A = [1, 2, 3, 5]

It looks pretty clear that the desired answer is 4, but your function is giving None. It's because len(A) == 4 and thus, your loop condition is i < 4, which effectively enumerates i from 1 to 3.

Since you want to find out the missing number, you might as well stop the loop when i reaches the largest number in the list, rather than the length of the list, so:

while i < max(A):

would be right.