Missing Number

Problem

Given nums containing n distinct integers taken from the range 0 to n, return the single missing value from that range.

XOR every index together with every value so matching pairs cancel out and only the missing number remains. Runs in O(n) time with O(1) extra space.

Hint

XOR of a value with itself is 0, so start from n and XOR in each index and value.

case 1

in: [[3,0,1]]

expected: 2

case 2

in: [[0,1]]

expected: 2

case 3

in: [[9,6,4,2,3,5,7,0,1]]

expected: 8

case 4

in: [[0]]

expected: 1

case 5

in: [[1]]

expected: 0

Starter codePython

def missing_number(nums):
    # Your code here
    pass

5 test cases · run your code against them in the editor