algorithms/binary/missing_integer.py at main · dichev/algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
"""
# Missing Number
You are given an array nums containing n distinct integers from
the range [0, n]. One number in this range is missing from the
array. Find and return the missing number.
-----
for n = 5
range         nums
0  000       ^ 000 = 000
1  001       ^ 001 = 000
2  010       ^ 010 = 000
3  011  missing    = 011
4  100       ^ 100 = 000
-------
"""#

from functools import reduce
from operator import xor


def missing_number_bitwise(nums):
    n = len(nums)
    full = reduce(xor, range(n + 1))
    partial = reduce(xor, nums)
    return full ^ partial  # (0^1^2^3^4)^(0^1^2^4) = (0^0) ^ (1^1) ^ (2^2) ^ 3 ^ (4^4) = 0 ^ 0 ^ 0 ^ 3 ^ 0


def missing_number(nums):
    n = len(nums)
    expected = n*(n+1)/2 # arithmetic sum, equal to: sum(range(n+1))
    missing = expected - sum(nums)
    return missing


if __name__ == '__main__':
    from utils import test
    test(missing_number_bitwise([0,1,3]), 2)
    test(missing_number_bitwise([3,0,1]), 2)
    test(missing_number_bitwise([1,2]), 0)
    test(missing_number_bitwise([9, 6, 4, 2, 3, 5, 7, 0, 1]), 8)
    test(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1]), 8)

    from utils import plot_time_complexity
    plot_time_complexity(missing_number, lambda n: list(range(n-1)) + [n])
    plot_time_complexity(missing_number_bitwise, lambda n: list(range(n-1)) + [n])