The array holds n distinct numbers taken from 0 to n. Exactly one number is missing, so return it.
DSA Animator › DSA Revision › Binary Search › Missing Number
Remember: expected sum minus actual sum gives the missing number. XOR of indexes and values is the overflow-safe twin. The video solves Missing Number (LeetCode 268, Easy) with the Math / XOR pattern from the Binary Search topic, and you can replay every step in the interactive Missing Number animation.
The array holds n distinct numbers taken from 0 to n. Exactly one number is missing, so return it.
For 3, 0, 1, n is 3, so the numbers should be 0 to 3. The missing one is 2.
Sorting and scanning is O of n log n, and a hash set uses O of n space. If the array is already sorted, binary search on whether index equals value also works.
The sum of 0 to n is n times n plus 1, over 2. Subtract the actual sum of the array, and what is left is the missing number. An exclusive or of all indexes and values works the same way, without any risk of overflow.
n is 3, so the expected sum is 3 times 4 over 2, which is 6. The actual sum is 3 plus 0 plus 1, which is 4. 6 minus 4 is 2. The missing number is 2.
In code, start with n times n plus 1, over 2. Subtract every number in the array. Return what remains, so it's O of n time and O of 1 space.
Remember: expected sum minus actual sum gives the missing number. XOR of indexes and values is the overflow-safe twin.