python - How to find a missing number from a list?

Question

How do I find the missing number from a sorted list the pythonic way?

a=[1,2,3,4,5,7,8,9,10]

I have come across this post but is there a more and efficient way to do this?

Answer 1

>>> a=[1,2,3,4,5,7,8,9,10]
>>> sum(xrange(a[0],a[-1]+1)) - sum(a)
6

alternatively (using the sum of AP series formula)

>>> a[-1]*(a[-1] + a[0]) / 2 - sum(a)
6

For generic cases when multiple numbers may be missing, you can formulate an O(n) approach.

>>> a=[1,2,3,4,7,8,10]
>>> from itertools import imap, chain
>>> from operator import sub
>>> print list(chain.from_iterable((a[i] + d for d in xrange(1, diff))
                        for i, diff in enumerate(imap(sub, a[1:], a))
                        if diff > 1))
[5, 6, 9]

Answer 2

This should work:

a = [1, 3, 4, 5, 7, 8, 9, 10]
b = [x for x in range(a[0], a[-1] + 1)]
a = set(a)
print(list(a ^ set(b)))
>>> [2, 6]

Answer 3

1 + 2 + 3 + ... + (n - 1) + n = (n) * (n + 1)/2

so the missing number is:

(a[-1] * (a[-1] + 1))/2 - sum(a)

Answer 4

set(range(a[len(a)-1])[1:]) - set(a)

Take the set of all numbers minus the set of given.

Answer 5

And another itertools way:

from itertools import count, izip

a=[1,2,3,4,5,7,8,9,10]
nums = (b for a, b in izip(a, count(a[0])) if a != b)
next(nums, None)
# 6

Answer 6

This will handle the cases when the first or last number is missing.

>>> a=[1,2,3,4,5,7,8,9,10]
>>> n = len(a) + 1
>>> (n*(n+1)/2) - sum(a)
6

Answer 7

If many missing numbers in list:

>>> a=[1,2,3,4,5,7,8,10]
>>> [(e1+1) for e1,e2 in zip(a, a[1:]) if e2-e1 != 1]
[6, 9]

Answer 8

def find(arr):
        for x in range(0,len(arr) -1):
                if arr[x+1] - arr[x] != 1:
                        print arr[x] + 1

Answer 9

Simple solution for the above problem, it also finds multiple missing elements.

a = [1,2,3,4,5,8,9,10]
missing_element = []
for i in range(a[0], a[-1]+1):
    if i not in a:
        missing_element.append(i)

print missing_element

o/p: [6,7]

Answer 10

Here is the simple logic for finding mising numbers in list.

l=[-10,-5,2,4,5,9,20]
s=l[0]
e=l[-1]
x=sorted(range(s,e+1))
l_1=[]
for i in x:
    if i not in l:
        l_1.append(i)
print(l_1)

Answer 11

def findAllMissingNumbers(a):
   b = sorted(a)
   return list(set(range(b[0], b[-1])) - set(b))

Answer 12

A simple list comprehension approach that will work with multiple (non-consecutive) missing numbers.

def find_missing(lst):
    """Create list of integers missing from lst."""
    return [lst[x] + 1 for x in range(len(lst) - 1) 
            if lst[x] + 1 != lst[x + 1]]

Answer 13

I used index position. this way i compare index and value.

a=[0,1,2,3,4,5,7,8,9,10]

for i in a:
  print i==a.index(i)

Answer 14

There is a perfectly working solution by @Abhiji. I would like to extent his answer by the option to define a granularity value. This might be necessary if the list should be checked for a missing value > 1:

from itertools import imap, chain
from operator import sub

granularity = 3600
data = [3600, 10800, 14400]

print list(
  chain.from_iterable(
    (data[i] + d for d in xrange(1, diff) if d % granularity == 0) 
      for i, diff in enumerate(imap(sub, data[1:], data)) 
        if diff > granularity
  )
)

The code above would produce the following output: [7200].

As this code snipped uses a lot of nested functions, I'd further like to provide a quick back reference, that helped me to understand the code:

• Python enumerate()
• Python imap()
• Python chain.from_iterable()

Answer 15

Less efficient for very large lists, but here's my version for the Sum formula:

def missing_number_sum(arr):
    return int((arr[-1]+1) * arr[-1]/2) - sum(arr)

Answer 16

If the range is known and the list is given, the below approach will work.

a=[1,2,3,4,5,7,8,9,10]
missingValues = [i for i in range(1, 10+1) if i not in a]
print(missingValues)

# o/p: [6] 

Answer 17

set(range(1,a[-1])) | set(a)

Compute the union of two sets.