#338 Counting Bits
the problem
In plain words
Return an array ans of length n + 1 where ans[i] is the number of 1-bits in i, for every i from 0 to n. Can you do it in O(n) without a built-in popcount?
in n = 2
out [0,1,1]
in n = 5
out [0,1,1,2,1,2]
- 0 ≤ n ≤ 10⁵
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternBit tricks (shift, mask, lowest set bit)1D DP
i >> 1 is i with its last bit removed, and it is smaller, so its answer is already known. Add back the last bit: ans[i] = ans[i >> 1] + (i & 1).
solutions
From brute force to optimal
Run the x &= x − 1 counting loop separately for each i.
- For i in 0..n: count bits of i with
x &= x − 1.
Each i has at most log₂ n + 1 one-bits.
Besides the output array.
class Solution { public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 0; i <= n; i++) { int x = i, count = 0; while (x != 0) { x &= x - 1; count++; } // Kernighan per number ans[i] = count; } return ans; }}Reuse the answer for i without its last bit.
- ans[0] = 0.
- For i = 1..n: ans[i] = ans[i >> 1] + (i & 1).
One O(1) step per number.
Only the output array.
class Solution { public int[] countBits(int n) { int[] ans = new int[n + 1]; // ans[0] = 0 for (int i = 1; i <= n; i++) { ans[i] = ans[i >> 1] + (i & 1); // drop last bit, add it back } return ans; }}Dry run
i & (i − 1) is i with its lowest 1 erased. It is smaller and has exactly one fewer 1-bit.
- For i = 1..n: ans[i] = ans[i & (i − 1)] + 1.
One O(1) step per number.
Only the output array.
class Solution { public int[] countBits(int n) { int[] ans = new int[n + 1]; for (int i = 1; i <= n; i++) { ans[i] = ans[i & (i - 1)] + 1; // i & (i-1) has exactly one 1-bit fewer } return ans; }}in the room
How to say it in the interview
talk track
- Start with "popcount each number". Then notice that smaller numbers are solved first, which is the DP signal.
- Explain the recurrence with an example: 13 = 1101 and 13 >> 1 = 110 = 6, so ans[13] = ans[6] + 1 = 3.
traps
- Writing
ans[i >> 1] + i & 1without brackets:+binds tighter than&, so Java computes(ans[i >> 1] + i) & 1. - Allocating
new int[n]— you need n + 1 slots, for 0..n. - Calling
Integer.bitCountin a loop: correct, but the question asks you to do it without a built-in.
what they ask next
Follow-ups
Which DP chapter idea is this?
A 1D DP where each state depends on one smaller state. The "smaller" here is i >> 1 instead of i − 1.
before you submit
Edge cases to test
- n = 0 → [0].
- Every power of two has exactly one 1-bit.
- n = 100,000: a popcount per number still passes, but the O(n) DP is the clean answer.
practise next
Similar problems
- #191Number of 1 BitsEasyin Bits
- #70Climbing StairsEasyin Dynamic Programming
- #779K-th Symbol in GrammarMediumin Recursion