DSA AnimatorDSA animations
Missing Number LC #268 Easy Binary Search · Sorted Array
Problem

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Example 1
Input: nums = [0,1,3]
Output: 2
Explanation: After sorting: [0,1,3]. nums[2]=3 > 2=index → gap is to the left. Answer is 2.
Example 2
Input: nums = [0,1,2,3,4,5,6,7,9]
Output: 8
Example 3
Input: nums = [1,2,3]
Output: 0
Explanation: After sorting: [1,2,3]. nums[0]=1 > 0=index → gap is immediately to the left at index 0.
Constraints: n == nums.length  |  1 ≤ n ≤ 10⁴  |  0 ≤ nums[i] ≤ n  |  All numbers are unique.
Try Examples
Custom:
Sorted Array (Index vs Value)
nums[i] == i (value matches index) nums[i] > i (gap is to the LEFT) mid pointer missing gap
Gap Detector — nums[mid] vs mid
nums[mid]
—
vs
Waiting for first step…
mid
—
MISSING: ?
Variables
lo
—
hi
—
mid
—
nums[mid]
—
nums[mid] > mid?
—
Step Logic
Press ▶ Play or Next Step to begin the animation.
🎉
Ready
0 / 0
Select an example above and press Play.
Algorithm
1
Sort the array. Set lo = 0, hi = nums.length.
2
Compute mid = lo + (hi - lo) / 2.
3
If nums[mid] > mid: gap is in the LEFT half → set hi = mid.
4
Else: gap is in the RIGHT half → set lo = mid + 1.
5
When lo == hi, that index is the missing number — return lo.
Time
O(n log n)
Space
O(1)
Why Binary Search Works

After sorting, if no number is missing before index i, then nums[i] == i. The missing number creates a shift: every element at or after the gap satisfies nums[i] == i + 1. This is a monotone predicate — perfect for binary search. nums[mid] > mid tells us the gap happened at or before mid, so we shrink the search space left. Otherwise it is strictly to the right.

How to solve Missing Number

LeetCode 268 · Easy · Binary Search · Pattern: Math / XOR

Why the obvious approach is slow

Sorting and scanning is O(n log n), and a hash set uses O(n) space. If the array is already sorted, binary search on whether index equals value also works.

The key idea

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.

Remember

Expected sum minus actual sum gives the missing number. XOR of indexes and values is the overflow-safe twin.

Run the animation above on your own input, or watch the 1:13 video explanation of Missing Number with a dry run and Java code.

More Binary Search problems