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?

There is a generalization of this problem! Refer the problem: http://stackoverflow.com/questions/3492302/easy-interview-question-got-harder-given-numbers-1-100-find-the-missing-numbe — Sreejith Menon, Jan 08 '17 at 02:29

Abhijit · Accepted Answer · 2016-03-10T08:44:06.547

25

>>> 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]

edited Mar 10 '16 at 08:44

answered Dec 21 '13 at 11:07

Abhijit

62,056
18
131
204

What if 1, 2, 3 are missing? – thefourtheye Dec 21 '13 at 11:08
3

Question says `How to find missing number` and not `How to find amissing numbers` – Abhijit Dec 21 '13 at 11:08
1

@thefourtheye: Check my update for a generic case with multiple gaps – Abhijit Dec 21 '13 at 11:23
If the missing number is the highest or lowest one, ie. either 1 or 10 in his list is missing, then the above algorithm doesn't work, but that's nitpicking. – Lasse V. Karlsen Dec 21 '13 at 11:33
@LasseV.Karlsen: Then we can argue if those numbers are actually missing, or, they are not supposed to be in the list. – Abhijit Dec 21 '13 at 11:35
How about `set(a).symmetric_difference(xrange(a[0], a[-1] + 1))` for the second example? – Jon Clements Dec 21 '13 at 11:58
@JonClements: I do not have timing data, to suport if set operation might be faster. Also, in any case the final result needs to be sorted – Abhijit Dec 21 '13 at 12:04
@Abhijit Not necessarily... that's a constraint you've implied yourself when offering the multiple number solution. I was just offering a more readable (not necessarily faster) - and a sort afterwards isn't exactly difficult :) – Jon Clements Dec 21 '13 at 12:10
I get `sub is not defined` – Jorjon Mar 10 '16 at 08:33
@Veehmot: Just import sub from operator as `from operator import sub` – Abhijit Mar 10 '16 at 08:43

score 15 · Answer 2 · edited Jun 13 '21 at 08:55

15

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]

edited Jun 13 '21 at 08:55

Camilo Martinez M.

1,420
1
7
21

answered Dec 02 '15 at 15:03

Samman Thapa

159
1
3

1

Elegant solution, which doesn't involve extra modules (which is the case with the solution provided by @Abhijit). The only issue (not sure if it exists!) is the conversion to a set. If the list already contains unique numbers, I'm not sure what the performance impact would be when the `set()` conversion is applied. Sadly the `^` operator only works on sets hence the conversion needs to take place even when one knows that the list is actually a set (though stored as a list). – rbaleksandar Mar 10 '20 at 10:11
@rbaleksandar I believe the set allows one to perform the symmetric difference between the two "lists". – JMortey Mar 24 '21 at 18:08
Hi, sorry for jumping into your answer this late. Wondering if you could enlighten me why for the range, the last element need to be added with a value of 1? I tried without it and I am still able to get the same answer.. – dissidia May 28 '22 at 18:35
@dissidia `range(0,10)` would only cover the values from 0 to 9, inclusive. To also cover 10, 1 is added to the last value of `a`. Of course, it doesn't really matter because if 10 were missing from `a`, how would we know about that? – Raketenolli Jun 15 '22 at 14:47

score 8 · Answer 3 · edited Dec 21 '13 at 12:08

8

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

so the missing number is:

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

edited Dec 21 '13 at 12:08

Steve P.

14,489
8
42
72

answered Dec 21 '13 at 11:08

Gabriel

3,564
1
27
49

Your answer is correct, but given your first sentence, it would make a lot more sense if you actually used that fact in the answer, ie remove the first part and replace it with the product... – Steve P. Dec 21 '13 at 11:58
Modified it to be relevant to the problem at hand. – Steve P. Dec 21 '13 at 12:08

score 7 · Answer 4 · answered Dec 21 '13 at 11:11

7

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

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

answered Dec 21 '13 at 11:11

Saša Šijak

8,717
5
47
82

`range(a[0],a[-1]+1)` ? – steinerkelvin Dec 21 '13 at 11:14
@kelvinss I was thinking that his array is beginning from 1 always because he asked what if 1,2,3 are missing – Saša Šijak Dec 21 '13 at 11:18
I realized that the `+1` in the second argument doesn't matter. But I think `range(1,a[-1])` is more clear. – steinerkelvin Dec 21 '13 at 11:24
1

I believe this is the most concise solution that solves the general case. The other algorithms mentioned don't account for gaps. E.g. `a=[1, 2, 4, 99]`. Your method handles this appropriately. – James Feb 11 '14 at 15:27

score 7 · Answer 5 · answered Dec 21 '13 at 11:49

7

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

answered Dec 21 '13 at 11:49

Jon Clements

138,671
33
247
280

score 2 · Answer 6 · answered Jan 24 '18 at 06:47

2

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

answered Jan 24 '18 at 06:47

JMortey

55
7

score 1 · Answer 7 · answered Dec 21 '13 at 11:14

1

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]

answered Dec 21 '13 at 11:14

ndpu

22,225
6
54
69

1

You might want to say `e2-e1 != 1` – thefourtheye Dec 21 '13 at 11:16
What if `a=[1,2,3,4,5,8,10]` – Abhijit Dec 21 '13 at 11:24

score 1 · Answer 8 · edited Jun 08 '15 at 02:01

1

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

edited Jun 08 '15 at 02:01

josliber

43,891
12
98
133

answered Jun 08 '15 at 01:45

Prat_yow

23
1
8

score 1 · Answer 9 · answered Jul 06 '18 at 13:02

1

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]

answered Jul 06 '18 at 13:02

Venkatesh_CTA

120
10

score 1 · Answer 10 · answered Dec 09 '18 at 17:36

1

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)

answered Dec 09 '18 at 17:36

BrahmaReddy Seelam

11
1

all missing numbers will be added to the ( l_1 ) list. – BrahmaReddy Seelam Dec 09 '18 at 17:39

score 1 · Answer 11 · edited Apr 28 '21 at 20:17

1

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

edited Apr 28 '21 at 20:17

David Buck

3,752
35
31
35

answered Mar 08 '20 at 05:41

Shyambeer Singh

318
2
9

score 1 · Answer 12 · answered Feb 13 '22 at 18:47

1

L=[-5,1,2,3,4,5,7,8,9,10,13,55]

missing=[]

for i in range(L[0],L[-1]):
    if i not in L:
        missing.append(i)
print(missing)

answered Feb 13 '22 at 18:47

Joe121

62
5

Hi Joe, with 17 other answers already present, it would be great if you could add an explanation to your code to help us understand how it is different from other answers and how it solves the problem in the way that other answers dont. Thanks! – Simas Joneliunas Feb 18 '22 at 01:36

score 0 · Answer 13 · answered Dec 21 '13 at 11:16

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]]

score 0 · Answer 14 · answered Jun 16 '18 at 20:08

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:

score 0 · Answer 15 · edited Mar 05 '19 at 20:39

0

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)

edited Mar 05 '19 at 20:39

dbc

104,963
20
228
340

answered Mar 05 '19 at 20:36

Dylan Maulucci

11
2

score 0 · Answer 16 · answered Feb 15 '21 at 11:24

0

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]

answered Feb 15 '21 at 11:24

laplace

656
7
15

score -1 · Answer 17 · answered Dec 21 '13 at 12:29

-1

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

Compute the union of two sets.

answered Dec 21 '13 at 12:29

M4rtini

13,186
4
35
42

score -1 · Answer 18 · edited Jun 20 '17 at 18:23

-1

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)

edited Jun 20 '17 at 18:23

kuro

3,214
3
15
31

answered Jun 20 '17 at 17:11

Andre

1
2

1

Doesn't give the expected result. – kuro Jun 20 '17 at 17:22
This is not scalable at all and will not work if the array numerals are far off from the index. – Arka Mukherjee Oct 19 '21 at 02:24

How to find a missing number from a list?

18 Answers18

Linked

Related