BeginnerMath for DSAUsed everywhere
1 + 2 + … + n = n(n+1)/2
This one formula explains why “for j in range(i, n)” inside a loop is O(n²), and it solves Missing Number in one line.
The idea
Pair the first and last numbers: 1 + n, 2 + (n−1), 3 + (n−2)… every pair sums to n + 1, and there are n/2 pairs. So the total is n(n+1)/2.
It appears whenever an inner loop shrinks by one each time: n + (n−1) + … + 1 steps, which is about n²/2, so O(n²). It's also the number of subarrays of an array of length n.
Worked example
Missing Number: [3, 0, 1] (numbers 0..3, one missing)
- Expected total of 0..3 = 3 · 4 / 2 = 6.
- Actual total = 3 + 0 + 1 = 4.
- Missing = 6 − 4 = 2.
In code (Python)
def missing_number(nums):
n = len(nums)
return n * (n + 1) // 2 - sum(nums)
def count_subarrays(n):
return n * (n + 1) // 2 # n = 5 -> 15O(n) for Missing Number, O(1) extra space.
How to spot it
- Nested loops where the inner one starts at i or i + 1.
- “Find the missing / extra number in 0..n”, “how many subarrays / pairs”.
Common mistakes
- Forgetting it's n(n+1)/2, not n²/2: close for big n, wrong for exact answers.
- Overflow in Java/C++ when n is large: use a long.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →