Skip to content
LEETFLIX

Missing Number

EasyArrayHashingMathBinary searchBitmaskSorting
Solve on LeetCode

Easy · XOR 0..n against nums. Real solution for this problem — same player as the hand-authored deep-dives.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

LeetCode 268. Missing Number. The copyrighted prompt is on LeetCode. This page is a working XOR 0..n against nums for this problem: editable input, Python, Go, and a step-by-step animation.

Constraints

  • —Player inputs are capped so the animation stays readable.
  • —Match LeetCode's own constraints when you submit there.

Examples

Input

nums =
[3, 0, 1]

Output

2

02

Solution

Python and Go. The walkthrough below runs this same code.

Approach 1Optimal▶ Animated

XOR the range with the array

XOR every index 0..n with every value. Pairs cancel; the missing number is left.

The complete range is 0..n. The array is that range minus one value. XOR is how you subtract without summing.

Algorithm

  1. Start acc = n.
  2. XOR acc with each (i ^ nums[i]).
  3. Return acc.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def missingNumber(self, nums: list[int]) -> int:        acc = len(nums)        for i, x in enumerate(nums):            acc ^= i ^ x        return acc
Watch this run

03

Interactive walkthrough

Playing “XOR the range with the array”. Edit the input, hit Run, then scrub.

Approach: XOR the range with the array

Loading animation…