Missing Number

easyBit Manipulation+10 XPTime limit 2s

The array holds n distinct numbers taken from 0, 1, …, n — so exactly one number in that range is missing. Find it.

Input:

line 1: n
line 2: n distinct integers

Output: the missing number.

Constraints: 1 ≤ n ≤ 10⁵.

Two O(1)-memory tricks: the expected sum n(n + 1)/2 minus the actual sum — or XOR all indices 0…n with all values; every number present cancels out, leaving the missing one.

Sample input 1

3
3 0 1

Sample output 1

Sample input 2

2
0 1

Sample output 2

Sample input 3

9
9 6 4 2 3 5 7 0 1

Sample output 3

📖 Stuck? Learn the pattern

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…