Counting Bits
MediumReuse the answer for half the number
Problem
For every number from 0 to n, return the count of set bits.
Each number's 1-count is its half's count plus its last bit — build up from smaller numbers.
The idea
The bits of i are the bits of i >> 1 plus its own lowest bit, so bits[i] = bits[i >> 1] + (i & 1). Every answer builds on an already-computed smaller one, giving O(n) for the whole range.
The trick
- bits[i] = bits[i >> 1] + (i & 1).
- Equivalently bits[i] = bits[i & (i-1)] + 1.
- O(n) total, versus O(n log n) counting each independently.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — n=5 Values: 5.
1dp[0]=02for i in 1..n: dp[i]=dp[i>>1]+(i&1)Input
- array
- [5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 5
- Output:
- [0, 1, 1, 2, 1, 2]
- Explanation:
- Number of 1-bits for 0..5.
Example 2
- Input:
- n = 2
- Output:
- [0, 1, 1]
- Explanation:
- 0,1,1.
Example 3
- Input:
- n = 0
- Output:
- [0]
- Explanation:
- Just [0].
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.