BeginnerMath for DSAUsed everywhere
Powers of two you should know by heart
2¹⁰ ≈ 1 thousand, 2²⁰ ≈ 1 million, 2³⁰ ≈ 1 billion, 2³¹ − 1 is the int limit. They turn constraints into quick decisions.
The idea
2ⁿ doubles every step, so it explodes: 2¹⁰ = 1,024 ≈ 10³. Every 10 more doublings multiply by about a thousand. That gives instant estimates: 2²⁰ ≈ 10⁶, 2³⁰ ≈ 10⁹.
Use it both ways. A set of n items has 2ⁿ subsets, so trying all of them is fine for n ≤ 20 and hopeless for n = 40. And a 32-bit signed int holds up to 2³¹ − 1 = 2,147,483,647.
Worked example
Can I try every subset?
- n = 15 → 2¹⁵ ≈ 32,000 subsets: easily fine.
- n = 20 → 2²⁰ ≈ 1 million: fine.
- n = 40 → 2⁴⁰ ≈ 10¹²: far too slow. Think DP or meet-in-the-middle.
In code (Python)
def all_subsets(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 .. 2^n - 1
result.append([nums[i] for i in range(n) if mask >> i & 1])
return resultGenerating all subsets is O(n · 2ⁿ).
How to spot it
- Constraints like n ≤ 20 (subsets are fine) or values up to 2³¹ − 1 (watch for overflow).
Common mistakes
- Confusing 2ⁿ with n²: for n = 30 that's a billion versus 900.
- Summing two ints near 2³¹ in Java/C++ without a long.
Where it comes up
Go further
Up next for you · Beginner
“Have I seen this?” is a set →