Find the one missing number from 0 to n in O(1) space
A venue printed tickets numbered 0 through n for an event. At the door, the scanner recorded every ticket that was used, in arrival order. Exactly one ticket was never scanned. Implement findMissingNumber(scanned), which returns that ticket number.
findMissingNumber(scanned) // => the missing number
scanned has length n and holds n distinct integers from the range 0 to n (inclusive), in any order. Exactly one number in that range is absent.0 or n itself.n = 0, so the only ticket, 0, is missing.findMissingNumber([4, 0, 1, 2]);
// => 3
findMissingNumber([2, 1, 3]);
// => 0
findMissingNumber([0, 1, 2]);
// => 3 (n = 3, so the range is 0..3)
findMissingNumber([1]);
// => 0
findMissingNumber([]);
// => 0