codejump
EasyPythonJavaScriptTypeScript

Bits — Missing Number

AlgorithmsBit ManipulationMathArrays

solve(nums) — nums holds n distinct numbers taken from the range 0..n, so
exactly one number of that range is missing. Return it in O(n) time and O(1) space.

Two classic solutions: the sum n(n+1)/2 minus the sum of nums, or XOR. With XOR, combine
every index 0..n with every value: each number present appears twice and cancels, and the
missing one appears only as an index.

Examples

solve([3,0,1])              → 2
solve([0,1])                → 2
solve([9,6,4,2,3,5,7,0,1])  → 8

Sample tests

Test #1Missing in the middle
Input: [[3,0,1]]
Output: 2
Test #2Missing is n
Input: [[0,1]]
Output: 2
Test #3Longer array
Input: [[9,6,4,2,3,5,7,0,1]]
Output: 8
← All challenges