215. Counting Bits
🔗 LeetCode Problem: 338. Counting Bits
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Bit Manipulation, DP - 1D
Problem Statement
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0 (0 ones)
1 --> 1 (1 one)
2 --> 10 (1 one)
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0 (0 ones)
1 --> 1 (1 one)
2 --> 10 (1 one)
3 --> 11 (2 ones)
4 --> 100 (1 one)
5 --> 101 (2 ones)
Constraints:
- 0 <= n <= 10^5
Follow-up:
- Can you do it in linear time O(n)?
- Can you do it without using built-in functions like Integer.bitCount()?
- Can you solve it using only O(1) extra space (excluding the output array)?
🌳 Visual Understanding - The Complete Picture
The Problem We're Solving:
Given: n = 5
Find: Count of 1's in binary for 0, 1, 2, 3, 4, 5
Let's see the binary representations:
0 = 0 --> 0 ones
1 = 1 --> 1 one
2 = 10 --> 1 one
3 = 11 --> 2 ones
4 = 100 --> 1 one
5 = 101 --> 2 ones
Output: [0, 1, 1, 2, 1, 2]
QUESTION: Do we need to count bits for each number independently?
Or is there a PATTERN we can exploit? 🤔
The Hidden Pattern - Powers of 2:
Let's look at numbers organized by powers of 2:
Power of 2: 2^0 = 1
Numbers: 0, 1
Binary: 0, 1
Counts: 0, 1
Power of 2: 2^1 = 2
Numbers: 2, 3
Binary: 10, 11
Counts: 1, 2
Power of 2: 2^2 = 4
Numbers: 4, 5, 6, 7
Binary: 100, 101, 110, 111
Counts: 1, 2, 2, 3
Power of 2: 2^3 = 8
Numbers: 8, 9, 10, 11, 12, 13, 14, 15
Binary: 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111
Counts: 1, 2, 2, 3, 2, 3, 3, 4
PATTERN EMERGING! 🔍
The AHA Moment - Relationship Discovery:
Let's compare numbers with their "previous counterparts":
For range [2, 3] (power 2^1):
2 = 10 = 1 + 0 --> count(2) = 1 + count(0) = 1 + 0 = 1 ✓
3 = 11 = 1 + 1 --> count(3) = 1 + count(1) = 1 + 1 = 2 ✓
For range [4, 7] (power 2^2):
4 = 100 = 1 + 00 --> count(4) = 1 + count(0) = 1 + 0 = 1 ✓
5 = 101 = 1 + 01 --> count(5) = 1 + count(1) = 1 + 1 = 2 ✓
6 = 110 = 1 + 10 --> count(6) = 1 + count(2) = 1 + 1 = 2 ✓
7 = 111 = 1 + 11 --> count(7) = 1 + count(3) = 1 + 2 = 3 ✓
For range [8, 15] (power 2^3):
8 = 1000 = 1 + 000 --> count(8) = 1 + count(0) = 1 + 0 = 1 ✓
9 = 1001 = 1 + 001 --> count(9) = 1 + count(1) = 1 + 1 = 2 ✓
10 = 1010 = 1 + 010 --> count(10) = 1 + count(2) = 1 + 1 = 2 ✓
11 = 1011 = 1 + 011 --> count(11) = 1 + count(3) = 1 + 2 = 3 ✓
12 = 1100 = 1 + 100 --> count(12) = 1 + count(4) = 1 + 1 = 2 ✓
13 = 1101 = 1 + 101 --> count(13) = 1 + count(5) = 1 + 2 = 3 ✓
14 = 1110 = 1 + 110 --> count(14) = 1 + count(6) = 1 + 2 = 3 ✓
15 = 1111 = 1 + 111 --> count(15) = 1 + count(7) = 1 + 3 = 4 ✓
THE PATTERN:
count(i) = 1 + count(i - offset)
where offset is the largest power of 2 ≤ i
Visualizing the Pattern - Binary Building Blocks:
Think of it this way:
Numbers [0, 1]:
0 = 0
1 = 1
Pattern: Base case
Numbers [2, 3]: (Add MSB '1' to [0, 1])
2 = 1 + 0 (Add '1' to 0)
3 = 1 + 1 (Add '1' to 1)
┌─────────────────┐
│ MSB = 1 │
│ Rest = [0, 1] │
└─────────────────┘
Numbers [4, 7]: (Add MSB '1' to [0, 3])
4 = 1 + 00 (Add '1' to 0)
5 = 1 + 01 (Add '1' to 1)
6 = 1 + 10 (Add '1' to 2)
7 = 1 + 11 (Add '1' to 3)
┌─────────────────┐
│ MSB = 1 │
│ Rest = [0, 3] │
└─────────────────┘
Numbers [8, 15]: (Add MSB '1' to [0, 7])
8 = 1 + 000 (Add '1' to 0)
9 = 1 + 001 (Add '1' to 1)
10 = 1 + 010 (Add '1' to 2)
11 = 1 + 011 (Add '1' to 3)
12 = 1 + 100 (Add '1' to 4)
13 = 1 + 101 (Add '1' to 5)
14 = 1 + 110 (Add '1' to 6)
15 = 1 + 111 (Add '1' to 7)
┌─────────────────┐
│ MSB = 1 │
│ Rest = [0, 7] │
└─────────────────┘
INSIGHT: Each range REPEATS previous pattern
with an extra '1' bit! 💡
The Offset Tracking Approach:
Instead of computing offset every time,
we can TRACK when we hit a new power of 2!
Observation:
- offset starts at 1
- offset doubles when we process 2*offset numbers
Example walkthrough:
i = 0: count[0] = 0 (base case)
offset = 1
i = 1: count[1] = 1 (base case)
We've processed offset (1) numbers since last power
Next power: offset *= 2 = 2
i = 2: count[2] = 1 + count[2-2] = 1 + count[0] = 1
offset = 2
i = 3: count[3] = 1 + count[3-2] = 1 + count[1] = 2
We've processed offset (2) numbers since offset started
Next power: offset *= 2 = 4
i = 4: count[4] = 1 + count[4-4] = 1 + count[0] = 1
offset = 4
i = 5: count[5] = 1 + count[5-4] = 1 + count[1] = 2
offset = 4
i = 6: count[6] = 1 + count[6-4] = 1 + count[2] = 2
offset = 4
i = 7: count[7] = 1 + count[7-4] = 1 + count[3] = 3
We've processed offset (4) numbers since offset started
Next power: offset *= 2 = 8
And so on...
This is DYNAMIC PROGRAMMING! 🎯
- Each result depends on previous results
- Build answer bottom-up
- Reuse computed values
🧠 The Solution Evolution
Approach 0: Brute Force (What NOT to do)
For each number i from 0 to n:
Convert i to binary
Count the '1's in binary representation
Store in result array
Time: O(n * log n) - for each of n numbers, count bits in log n time
Space: O(1) excluding output
This works but IGNORES the beautiful pattern! 😞
Approach 1: Built-in Function
public int[] countBits(int n) {
int[] ans = new int[n + 1];
for (int i = 0; i <= n; i++) {
ans[i] = Integer.bitCount(i);
}
return ans;
}
Time: O(n) - depends on implementation
Space: O(1) excluding output
This works but we're asked NOT to use built-in functions!
And we're missing the learning! 🎓
Approach 2: Brian Kernighan's Algorithm
Concept: For any number i,
i & (i-1) removes the rightmost '1' bit
Example:
12 = 1100
11 = 1011
--------
12 & 11 = 1000 (removed rightmost 1)
So: count(i) = count(i & (i-1)) + 1
This is also DP! We use previously computed count! 🎯
Approach 3: Power of 2 Offset (Optimal!)
Concept: Use the pattern we discovered!
count(i) = 1 + count(i - offset)
where offset = largest power of 2 ≤ i
Track offset and double it at right times!
This is the CLEANEST DP approach! ✨
Approach 4: Most Significant Bit (MSB)
Concept: Every number can be seen as:
i = 2^k + remainder
count(i) = 1 + count(remainder)
where remainder = i - 2^k
Find MSB position, use it to find offset!
Same idea, different computation! 🎯
🎯 Solution 1: Brian Kernighan's Algorithm
The Bit Manipulation Insight:
Key Property:
i & (i-1) removes the rightmost '1' bit from i
Proof:
Let i = ...10...0 (some 1 followed by zeros)
Then i-1 = ...01...1 (flip rightmost 1 to 0, all trailing 0s to 1)
i & (i-1) = ...00...0 (AND makes rightmost 1 become 0)
Examples:
6 = 110
5 = 101
6 & 5 = 100 (removed rightmost 1)
12 = 1100
11 = 1011
12 & 11 = 1000 (removed rightmost 1)
7 = 111
6 = 110
7 & 6 = 110 (removed rightmost 1)
The DP Recurrence:
Since i & (i-1) has exactly ONE less '1' bit than i:
count(i) = count(i & (i-1)) + 1
Base case:
count(0) = 0 (no bits set)
This is DP because:
- We build from smaller to larger
- Each result uses previous results
- i & (i-1) < i, so it's already computed!
Implementation:
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
// Base case
ans[0] = 0;
// Fill using DP recurrence
for (int i = 1; i <= n; i++) {
// Remove rightmost 1, add 1 to its count
ans[i] = ans[i & (i - 1)] + 1;
}
return ans;
}
}
Dry Run: n = 5
Initial: ans = [0, 0, 0, 0, 0, 0]
i = 1:
1 & 0 = 0
ans[1] = ans[0] + 1 = 0 + 1 = 1
ans = [0, 1, 0, 0, 0, 0]
i = 2:
2 = 10
1 = 01
2 & 1 = 00 = 0
ans[2] = ans[0] + 1 = 0 + 1 = 1
ans = [0, 1, 1, 0, 0, 0]
i = 3:
3 = 11
2 = 10
3 & 2 = 10 = 2
ans[3] = ans[2] + 1 = 1 + 1 = 2
ans = [0, 1, 1, 2, 0, 0]
i = 4:
4 = 100
3 = 011
4 & 3 = 000 = 0
ans[4] = ans[0] + 1 = 0 + 1 = 1
ans = [0, 1, 1, 2, 1, 0]
i = 5:
5 = 101
4 = 100
5 & 4 = 100 = 4
ans[5] = ans[4] + 1 = 1 + 1 = 2
ans = [0, 1, 1, 2, 1, 2]
Result: [0, 1, 1, 2, 1, 2] ✓
Complexity Analysis:
Time Complexity: O(n)
- Single pass through 0 to n
- Each operation O(1)
Space Complexity: O(1)
- Only output array (required)
- No extra space used
This is OPTIMAL! 🎯
🎯 Solution 2: Power of 2 Offset (Most Intuitive!)
The Pattern Recognition:
Numbers organized by highest bit:
Range [1, 1]: (2^0)
1 = 1
Range [2, 3]: (2^1)
2 = 10 = 1 + 0
3 = 11 = 1 + 1
Range [4, 7]: (2^2)
4 = 100 = 1 + 00
5 = 101 = 1 + 01
6 = 110 = 1 + 10
7 = 111 = 1 + 11
Range [8, 15]: (2^3)
8 = 1000 = 1 + 000
9 = 1001 = 1 + 001
10 = 1010 = 1 + 010
11 = 1011 = 1 + 011
12 = 1100 = 1 + 100
13 = 1101 = 1 + 101
14 = 1110 = 1 + 110
15 = 1111 = 1 + 111
INSIGHT:
count(i) = 1 + count(i - offset)
where offset is the start of current range
When to Update Offset:
Offset represents: largest power of 2 ≤ current number
Start: offset = 1
We double offset when:
- We've processed 'offset' numbers in current range
Tracking:
When i == offset * 2:
We've completed the range [offset, 2*offset-1]
Next range starts at 2*offset
So: offset *= 2
Example:
offset = 1, process i=1
i=2: offset *= 2 = 2 (new range [2,3])
offset = 2, process i=2,3
i=4: offset *= 2 = 4 (new range [4,7])
offset = 4, process i=4,5,6,7
i=8: offset *= 2 = 8 (new range [8,15])
Implementation:
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
// Base case
ans[0] = 0;
int offset = 1; // Tracks current power of 2
for (int i = 1; i <= n; i++) {
// Check if we've reached a new power of 2
if (i == offset * 2) {
offset *= 2;
}
// Use the pattern: count(i) = 1 + count(i - offset)
ans[i] = 1 + ans[i - offset];
}
return ans;
}
}
Dry Run: n = 10
Initial: ans = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
offset = 1
i = 1:
i != offset*2 (1 != 2)
ans[1] = 1 + ans[1-1] = 1 + ans[0] = 1 + 0 = 1
ans = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
i = 2:
i == offset*2 (2 == 2) → offset = 2
ans[2] = 1 + ans[2-2] = 1 + ans[0] = 1 + 0 = 1
ans = [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]
i = 3:
i != offset*2 (3 != 4)
ans[3] = 1 + ans[3-2] = 1 + ans[1] = 1 + 1 = 2
ans = [0, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0]
i = 4:
i == offset*2 (4 == 4) → offset = 4
ans[4] = 1 + ans[4-4] = 1 + ans[0] = 1 + 0 = 1
ans = [0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0]
i = 5:
i != offset*2 (5 != 8)
ans[5] = 1 + ans[5-4] = 1 + ans[1] = 1 + 1 = 2
ans = [0, 1, 1, 2, 1, 2, 0, 0, 0, 0, 0]
i = 6:
i != offset*2 (6 != 8)
ans[6] = 1 + ans[6-4] = 1 + ans[2] = 1 + 1 = 2
ans = [0, 1, 1, 2, 1, 2, 2, 0, 0, 0, 0]
i = 7:
i != offset*2 (7 != 8)
ans[7] = 1 + ans[7-4] = 1 + ans[3] = 1 + 2 = 3
ans = [0, 1, 1, 2, 1, 2, 2, 3, 0, 0, 0]
i = 8:
i == offset*2 (8 == 8) → offset = 8
ans[8] = 1 + ans[8-8] = 1 + ans[0] = 1 + 0 = 1
ans = [0, 1, 1, 2, 1, 2, 2, 3, 1, 0, 0]
i = 9:
i != offset*2 (9 != 16)
ans[9] = 1 + ans[9-8] = 1 + ans[1] = 1 + 1 = 2
ans = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 0]
i = 10:
i != offset*2 (10 != 16)
ans[10] = 1 + ans[10-8] = 1 + ans[2] = 1 + 1 = 2
ans = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2]
Result: [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2] ✓
Visual Pattern:
Index: 0 1 2 3 4 5 6 7 8 9 10
Value: 0 1 1 2 1 2 2 3 1 2 2
└─┘ └──┘ └─────┘ └────────┘
^ ^ ^ ^
[0] [1-1] [2-3] [4-7] [8-15]...
Pattern repeats with +1 for each new range! 🎯
Complexity Analysis:
Time Complexity: O(n)
- Single pass through 0 to n
- Offset check: O(1)
- Array access: O(1)
Space Complexity: O(1)
- Only output array (required)
- offset variable: O(1)
This is OPTIMAL and INTUITIVE! ✨
🎯 Solution 3: Least Significant Bit (LSB)
The Even/Odd Pattern:
Observation:
- Even numbers: LSB = 0
- Odd numbers: LSB = 1
For even number i:
i >> 1 removes the trailing 0
count(i) = count(i >> 1)
Example:
6 = 110
3 = 011 (6 >> 1)
count(6) = count(3) = 2 ✓
For odd number i:
i >> 1 removes the trailing 1
count(i) = count(i >> 1) + 1
Example:
5 = 101
2 = 010 (5 >> 1)
count(5) = count(2) + 1 = 1 + 1 = 2 ✓
Unified formula:
count(i) = count(i >> 1) + (i & 1)
Implementation:
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
ans[0] = 0;
for (int i = 1; i <= n; i++) {
// count(i) = count(i/2) + (i%2)
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
}
}
Dry Run: n = 7
Initial: ans = [0, 0, 0, 0, 0, 0, 0, 0]
i = 1 (odd):
1 >> 1 = 0
1 & 1 = 1
ans[1] = ans[0] + 1 = 0 + 1 = 1
ans = [0, 1, 0, 0, 0, 0, 0, 0]
i = 2 (even):
2 >> 1 = 1
2 & 1 = 0
ans[2] = ans[1] + 0 = 1 + 0 = 1
ans = [0, 1, 1, 0, 0, 0, 0, 0]
i = 3 (odd):
3 >> 1 = 1
3 & 1 = 1
ans[3] = ans[1] + 1 = 1 + 1 = 2
ans = [0, 1, 1, 2, 0, 0, 0, 0]
i = 4 (even):
4 >> 1 = 2
4 & 1 = 0
ans[4] = ans[2] + 0 = 1 + 0 = 1
ans = [0, 1, 1, 2, 1, 0, 0, 0]
i = 5 (odd):
5 >> 1 = 2
5 & 1 = 1
ans[5] = ans[2] + 1 = 1 + 1 = 2
ans = [0, 1, 1, 2, 1, 2, 0, 0]
i = 6 (even):
6 >> 1 = 3
6 & 1 = 0
ans[6] = ans[3] + 0 = 2 + 0 = 2
ans = [0, 1, 1, 2, 1, 2, 2, 0]
i = 7 (odd):
7 >> 1 = 3
7 & 1 = 1
ans[7] = ans[3] + 1 = 2 + 1 = 3
ans = [0, 1, 1, 2, 1, 2, 2, 3]
Result: [0, 1, 1, 2, 1, 2, 2, 3] ✓
📊 Approach Comparison
┌────────────────────────────────────────────────────────┐
│ COUNTING BITS - APPROACH COMPARISON │
├─────────────────┬──────────────┬───────────┬───────────┤
│ Approach │ Time │ Space │ Intuition │
├─────────────────┼──────────────┼───────────┼───────────┤
│ Brute Force │ O(n log n) │ O(1) │ Low │
│ Brian K. │ O(n) │ O(1) │ Medium │
│ Offset │ O(n) │ O(1) │ High ✓ │
│ LSB │ O(n) │ O(1) │ Medium │
└─────────────────┴──────────────┴───────────┴───────────┘
Best Choice for Interview: Offset (Solution 2)
- Most intuitive
- Easy to explain
- Shows pattern recognition
- Clear DP thinking
Alternative: Brian Kernighan (Solution 1)
- Bit manipulation insight
- Clean and elegant
- Shows advanced knowledge
🎯 Pattern Recognition - DP on Bit Patterns
Core DP Principle:
In DP, we solve problem by:
1. Finding subproblems
2. Finding recurrence relation
3. Building solution bottom-up
For Counting Bits:
Subproblem: count(i) for each i
Recurrence: Multiple ways!
- count(i) = count(i & (i-1)) + 1
- count(i) = 1 + count(i - offset)
- count(i) = count(i >> 1) + (i & 1)
Build: From 0 to n
Related Problems:
1. Number of 1 Bits (191)
Count bits in single number
Same as: ans[i] from this problem
Can use: i & (i-1) repeatedly
2. Binary Watch (401)
List times with k bits set
Use: Counting bits pattern
Constraint: count(hour) + count(minute) == k
3. Sum of Two Integers (371)
Add without + operator
Use: Bit manipulation
Related: Understanding binary operations
4. Reverse Bits (190)
Reverse bit order
Use: Bit manipulation
Pattern: Process bits one by one
When to Use This Pattern:
✓ Count bits in multiple numbers
✓ DP on bit patterns
✓ Exploit binary structure
✓ Build result incrementally
✓ Reuse previous computations
Pattern recognition:
If problem involves counting/using bits for range
→ Think DP + Bit Manipulation! 🔑
🆚 All Three Solutions - Complete Code
Solution 1: Brian Kernighan
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
ans[0] = 0;
for (int i = 1; i <= n; i++) {
// Remove rightmost 1, add 1 to count
ans[i] = ans[i & (i - 1)] + 1;
}
return ans;
}
}
Solution 2: Power of 2 Offset (Recommended!)
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
ans[0] = 0;
int offset = 1;
for (int i = 1; i <= n; i++) {
if (i == offset * 2) {
offset *= 2;
}
ans[i] = 1 + ans[i - offset];
}
return ans;
}
}
Solution 3: LSB (Least Significant Bit)
class Solution {
public int[] countBits(int n) {
int[] ans = new int[n + 1];
ans[0] = 0;
for (int i = 1; i <= n; i++) {
// count(i) = count(i/2) + (i%2)
ans[i] = ans[i >> 1] + (i & 1);
}
return ans;
}
}
🔍 Deep Dive - Why Each Solution Works
Brian Kernighan's Magic:
Why does i & (i-1) remove rightmost 1?
Binary perspective:
Any number i can be written as:
i = ...1 0 0 0 ... 0
↑ └─trailing zeros─┘
rightmost 1
Then i-1 flips everything from rightmost 1:
i-1 = ...0 1 1 1 ... 1
↑ └─all ones─┘
flipped
i & (i-1) makes rightmost 1 become 0:
result = ...0 0 0 0 ... 0
↑ └─all zeros─┘
cleared
Example walkthrough:
12 = 1100
11 = 1011
────
& = 1000 (cleared rightmost 1)
8 = 1000
7 = 0111
────
& = 0000 (cleared rightmost 1)
Each operation reduces count by exactly 1!
So: count(i) = count(i & (i-1)) + 1 ✓
Offset Pattern Deep Dive:
Why does pattern repeat with +1?
Think of binary representation:
Range [2^k, 2^(k+1) - 1] has highest bit at position k
All numbers in this range:
1 xxx...xxx
↑ └─k bits─┘
MSB
This MSB contributes 1 to count
Remaining k bits follow pattern of [0, 2^k - 1]
Example for k=2 (range [4,7]):
4 = 100 = 1·(2^2) + 0·(2^1) + 0·(2^0)
5 = 101 = 1·(2^2) + 0·(2^1) + 1·(2^0)
6 = 110 = 1·(2^2) + 1·(2^1) + 0·(2^0)
7 = 111 = 1·(2^2) + 1·(2^1) + 1·(2^0)
MSB = 1 (contributes 1 to count)
Rest = [0, 1, 2, 3] pattern repeats!
So: count(4+i) = 1 + count(i) for i ∈ [0,3]
This is: count(i) = 1 + count(i - offset) ✓
LSB Pattern Explanation:
Why does right shift pattern work?
Division by 2 (right shift):
- Even number: i = 2k → i >> 1 = k
Binary: ...x0 → ...x
Removed 0, count stays same
count(i) = count(k)
- Odd number: i = 2k+1 → i >> 1 = k
Binary: ...x1 → ...x
Removed 1, count decreases by 1
count(i) = count(k) + 1
Examples:
6 = 110 → 3 = 11
count(6) = count(3) = 2 ✓
7 = 111 → 3 = 11
count(7) = count(3) + 1 = 2 + 1 = 3 ✓
10 = 1010 → 5 = 101
count(10) = count(5) = 2 ✓
11 = 1011 → 5 = 101
count(11) = count(5) + 1 = 2 + 1 = 3 ✓
Unified: count(i) = count(i >> 1) + (i & 1) ✓
📝 Quick Revision Notes
🎯 Core Concept
Counting Bits uses Dynamic Programming to count 1's in binary representations efficiently. Instead of counting bits independently for each number, we exploit patterns in binary numbers. Three main approaches: (1) Brian Kernighan: Remove rightmost 1 bit using i & (i-1), (2) Offset Pattern: Numbers in range [2^k, 2^(k+1)) repeat previous pattern with +1, (3) LSB: Even/odd pattern using right shift. All achieve O(n) time, O(1) space. Pattern recognition is key!
⚡ Quick Implementation (Offset - Most Intuitive)
import java.util.Arrays;
public class Solution {
public int[] countBits(int n) {
// // Approach 1 - straight forward in-built metho
// return inBuilt(n);
// // Approach 2 - Brian Kernighan
// return algorithmic(n);
// Approach 3 - DP (suggested)
return offset(n);
}
private int[] offset(int n) {
// base cases
// 0 => 0
// --- i = 1
// 1 => 1
// --- i = 2 => pow(2,1) = 2 (ready for 2 numbers)
// 2 => 1 + count(0) = 1
// 3 => 1 + count(1) = 2
// --- i = 3 => pow(2,2) = 4 (ready for 4 numbers)
// 4 => 1 + count(0) = 1
// 5 => 1 + count(1) = 2
// 6 => 1 + count(2) = 2
// 7 => 1 + count(3) = 3
// --- i = 4 => pow(2,3) = 8 (ready for 8 numbers)
// 8 => 1 + count(0) = 1
// 9 => 1 + count(1) = 2
// 14 => 1 + count(6) = 3
// 15 => 1 + count(7) = 4
if (n == 0) {
return new int[] { 0 };
}
int[] res = new int[n + 1];
res[0] = 0;
int offset = 1;
for (int i = 1; i <= n; i++) {
if (i == offset * 2) {
offset *= 2; // New power of 2
}
res[i] = 1 + res[i - offset];
}
return res;
}
private int[] algorithmic(int n) {
int[] res = new int[n + 1];
res[0] = 0;
// 8 (1000), 9 (1001)
// 9 => i & (i-1) = 9 & 8 = 1000 (8) => Number of bits set in 8 + 1 = 2
// 10 => 10 & 9 => 1010 & 1001 = 1000 (8) => Number of bits set in 8 + 1 = 2
// 11 => 11 & 10 => 1011 & 1010 => 1010 (10) => Number of bits set in 10 + 1 = 3
// 12 => 12 & 11 => 1100 & 1011 => 1000 (8) => Number of bits set in 8 + 1 = 2
// Now, lets take 2 power case
// 8 => 8 & 7 => 1000 & 0111 => 0 (0) => Number of bits set in 0 + 1 = 1
for (int i = 1; i <= n; i++) {
res[i] = res[i & (i - 1)] + 1;
}
return res;
}
private int[] inBuilt(int n) {
int[] res = new int[n + 1];
for (int i = 0; i <= n; i++) {
res[i] = Integer.bitCount(i);
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(Arrays.toString(s.countBits(2)));
System.out.println(Arrays.toString(s.countBits(5)));
System.out.println(Arrays.toString(s.countBits(8)));
}
}
🔑 Key Insights
Pattern in Binary Numbers:
Range [0,1]: 0, 1 → counts: 0, 1
Range [2,3]: 10, 11 → counts: 1, 2 (= 1 + [0,1])
Range [4,7]: 100,101,110,111 → counts: 1,2,2,3 (= 1 + [0,1,2,3])
Range [8,15]: Similar pattern → counts: 1,2,2,3,2,3,3,4
Each range REPEATS previous with +1! 🎯
Three DP Recurrences:
1. Brian Kernighan:
count(i) = count(i & (i-1)) + 1
Removes rightmost 1 bit
2. Offset Pattern:
count(i) = 1 + count(i - offset)
offset = largest power of 2 ≤ i
3. LSB Pattern:
count(i) = count(i >> 1) + (i & 1)
Even: remove trailing 0
Odd: remove trailing 1, add 1
Bit Manipulation Tricks:
i & (i-1): Remove rightmost 1
i >> 1: Divide by 2
i & 1: Check if odd (LSB)
offset * 2: Next power of 2
🎪 Memory Aid
"Powers of 2 repeat the pattern!"
"Each range adds 1 to previous range!"
"Right shift reveals half the story!"
"DP on bits, not brute force!" ✨
⚠️ Don't Forget
- Base case:
ans[0] = 0(zero has no 1's) - Offset doubles when
i == offset * 2 - Pattern repeats: Each power of 2 starts fresh
- Three valid approaches, choose most intuitive
- O(n) time is optimal (can't do better)
🎯 Pattern Template - DP on Bit Patterns
When to Use:
✓ Problem involves bit counting
✓ Need to process range of numbers
✓ Can exploit binary structure
✓ Previous results help current computation
✓ Pattern in binary representation
Keywords:
- "count bits"
- "binary representation"
- "range of numbers"
- "optimal/efficient"
Generic Approach:
// Template for DP on Bit Patterns
public int[] dpOnBits(int n) {
int[] dp = new int[n + 1];
// Base case
dp[0] = 0;
// Choose your recurrence:
for (int i = 1; i <= n; i++) {
// Option 1: Use bit manipulation property
dp[i] = dp[i & (i-1)] + 1;
// Option 2: Use power of 2 pattern
// if (i == offset * 2) offset *= 2;
// dp[i] = 1 + dp[i - offset];
// Option 3: Use even/odd pattern
// dp[i] = dp[i >> 1] + (i & 1);
}
return dp;
}
🎉 Congratulations!
You've mastered Counting Bits - DP meets Bit Manipulation!
What You Learned:
✅ Pattern Recognition - Binary number patterns
✅ DP Thinking - Build on previous results
✅ Bit Manipulation - Three different approaches
✅ Optimization - O(n²) → O(n)
✅ Multiple Solutions - Different perspectives
✅ Clean Code - Elegant implementations
The Beautiful Insight:
BEFORE: Count bits for each number independently
→ O(n log n) time
AFTER: Recognize the pattern in binary!
→ O(n) time
The pattern:
Numbers [2^k, 2^(k+1)) = 1 + Numbers [0, 2^k)
Each range BUILDS on previous range!
This IS Dynamic Programming! 💡
Binary numbers aren't random!
They follow beautiful patterns! ✨
Interview Mastery:
Interviewer: "Count 1's in binary for 0 to n"
Your response:
"I can see three elegant DP approaches:
Approach 1 (Most Intuitive):
- Recognize power-of-2 pattern
- Each range [2^k, 2^(k+1)) repeats [0, 2^k)
- count(i) = 1 + count(i - offset)
- Track offset, double at boundaries
Approach 2 (Bit Magic):
- Use i & (i-1) to remove rightmost 1
- count(i) = count(i & (i-1)) + 1
- Very clean, one-liner recurrence
Approach 3 (LSB Pattern):
- Even/odd observation
- count(i) = count(i >> 1) + (i & 1)
- Divides problem by 2 each time
All are O(n) time, O(1) space!
I'll implement the offset approach
as it's most intuitive to explain..."
Shows complete understanding! 💯
Connection to Previous Patterns:
Problem 163: Binary Trie
- Store numbers as bit paths
- Navigate bits MSB to LSB
Problem 215: Counting Bits
- Count bits in numbers
- Exploit bit patterns
Both use: BIT MANIPULATION + DP! 🎯
Bit manipulation is a POWERFUL tool!
- For structure (Trie)
- For counting (DP)
- For optimization (patterns)
You've now mastered another beautiful intersection of DP and Bit Manipulation! 🏆✨🎯