DATA STRUCTURES • ALGORITHMS

Missing Number

Given an array containing n distinct numbers in the range [0, n], finding the one number that is missing from the sequence.

Time

O(N)

Space

O(1)

Key Principle 1

Gauss Sum Formula: n*(n+1)/2

Key Principle 2

XOR-based property

Key Principle 3

No extra memory required

Key Principle 4

Linear scan efficiency

MISSING_NUMBER_LAB
ARRAY:
Current Step
Finding missing number in [0, 3]. Gauss sum method.
Playback
Sum Tracker ⠿
EXPECTED6
ACTUAL0
DIFFERENCE6
Gauss Sum Logic ⠿
1int n = arr.size();
2int expected = n * (n + 1) / 2;
3int actual = 0;
4for (int x : arr) actual += x;
5return expected - actual;
3
idx 0
0
idx 1
1
idx 2

Loading Lab...