#151EasyArrays & Hashing· Sum Invariants

Missing Ticket Number

A theatre sells tickets numbered `0` through `n`, but only `n` people have walked through the door so far. Every scanned ticket number is different, and the scanner stores them in arrival order, so the log is unsorted. Exactly one number in the range `0..n` has not been scanned yet. Find it. A good answer does not sort the log and does not allocate a second structure the size of the log.

Input format

`tickets`: an array of `n` distinct integers, each between 0 and `n` inclusive.

Output format

A single integer: the one number in `0..n` that does not appear in `tickets`.

Examples

Input: tickets = [3, 0, 1]

Output: 2

Numbers 0 to 3 are expected. 0, 1 and 3 were scanned, so 2 is the one still missing.

Input: tickets = [0, 1]

Output: 2

With n = 2 the range is 0, 1, 2. The largest number can be the missing one.

Input: tickets = [9, 6, 4, 2, 3, 5, 7, 0, 1]

Output: 8

Nine tickets were scanned out of 0..9; the only absent value is 8.

Constraints

1 <= tickets.length <= 10^5
0 <= tickets[i] <= tickets.length
All values in `tickets` are distinct.

Study first

#arrays
#math
#bit-manipulation
#hash-table