Missing Number

An array holds n distinct numbers from the range [0, n]. Return the one number in that range that's missing.

A way to picture it

It's a sock drawer. Every number has a twin sock: its matching index. XOR is the washing machine where twins cancel out (x ^ x = 0). Throw everything in, and the only sock left is the one without a partner.

How to approach it

XOR every index 0..n with every value. Each value that's present cancels its matching index, leaving only the missing number.

Example

Input: {"nums":[3,0,1]}. Output: 2.

Complexity: O(n) time and O(1) space. One pass, one accumulator.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.