Missing Number¶

You are given a list of n-1 integers and these integers are in the range of 1 to n. There are no duplicates in list. One of the integers is missing in the list. Write an efficient code to find the missing integer.

Using SUM¶

In [1]:

def getMissingNum(arr):
    n = len(arr) + 1
    
    tot = n * (n + 1) / 2
    
    return int(tot - sum(arr))

In [2]:

arr = [1, 2, 4, 5, 6]
arr

Out[2]:

[1, 2, 4, 5, 6]

In [3]:

getMissingNum(arr)

Out[3]:

Using XOR¶

In [4]:

def findMissingNum(arr):
    x1, x2 = 0, 0
    
    for a in arr:    # XOR of all array element
        x1 ^= a
    
    for i in range(len(arr) + 2):    # XOR of numbers from 1 - n, +2 - 1 for missing value, 1 as range isn't inclusive
        x2 ^= i
        
    return x1 ^ x2

In [5]:

arr = [1, 2, 4, 5, 6]
arr

Out[5]:

[1, 2, 4, 5, 6]

In [6]:

findMissingNum(arr)

Out[6]:

Using Reduce with XOR¶

In [7]:

from functools import reduce

In [8]:

reduce(lambda x, y: x ^ y, [1, 2, 3, 5]) ^ reduce(lambda x, y: x ^ y, range(1, 4 + 2))

Out[8]: