Counting Bits
For every integer from 0 to n, count the 1 bits in its binary form. A small dynamic programming problem where each answer reuses an earlier one. Solve it below in Python or JavaScript, then read the walkthrough.
Problem
Given a non-negative integer n, return an array ans of length n + 1 where ans[i] is the number of 1s in the binary representation of i, for every i from 0 to n.
Example 1
- Input
- n = 3
- Output
- [0, 1, 1, 2]
0 is 0, 1 is 1, 2 is 10, and 3 is 11 in binary.
Example 2
- Input
- n = 6
- Output
- [0, 1, 1, 2, 1, 2, 2]
4 is 100, 5 is 101, and 6 is 110.
Example 3
- Input
- n = 0
- Output
- [0]
Constraints
- 0 ≤ n ≤ 10⁵
- The answer has exactly n + 1 entries.
- Aim for a single linear pass instead of counting each number's bits separately.
Practice
Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.
Get asked Counting Bits in a real interview?
Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.
How to solve Counting Bits
Pattern: DP over bits
Counting the bits of each number from scratch works, but it ignores that you're computing the answer for every number in order, so each smaller answer is already available.
Look at what shifting does. i >> 1 drops the last bit of i, giving a smaller number you've already solved. The only bit you lost is i & 1. So:
bits[i] = bits[i >> 1] + (i & 1)
For example, 13 is 1101. Shifting gives 6 (110, two 1s), and the dropped bit is 1, so 13 has three 1s. Each entry is one lookup and one addition.
Approach 1: Count each number separately
For each i, repeatedly check i & 1 and shift right until i is 0, counting ones. Easy to explain, but every number costs up to log n steps.
Time O(n log n) · Space O(1) besides the output
Approach 2: Lowest set bit
i & (i - 1) clears the lowest 1 bit of i, so bits[i] = bits[i & (i - 1)] + 1. Also linear, and a nice trick to know, though it is less obvious why it works than the shift version.
Time O(n) · Space O(1) besides the output
Approach 3: Shift right and add the last bit
Start with bits[0] = 0. For i from 1 to n, set bits[i] = bits[i >> 1] + (i & 1).
i >> 1 is always smaller than i, so its answer is already filled in.
Time O(n) · Space O(1) besides the output
| Approach | Time | Space |
|---|---|---|
| Count each number separately | O(n log n) | O(1) besides the output |
| Lowest set bit | O(n) | O(1) besides the output |
| Shift right and add the last bit | O(n) | O(1) besides the output |
Solution code
Try the practice editor first. Both solutions pass every test above.
Counting Bits solution in Python
def count_bits(n: int) -> list[int]:
bits = [0] * (n + 1)
for i in range(1, n + 1):
bits[i] = bits[i >> 1] + (i & 1) # drop the last bit, then add it back
return bitsCounting Bits solution in JavaScript
function countBits(n) {
const bits = new Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
bits[i] = bits[i >> 1] + (i & 1); // drop the last bit, then add it back
}
return bits;
}Common mistakes
- Returning an array of length n instead of n + 1. The range includes both 0 and n.
- Using a language built-in popcount and calling it the linear solution. It is fine to mention, but interviewers usually want the recurrence.
- Mixing up operator precedence in JavaScript: `i & 1 + x` parses as `i & (1 + x)`. Wrap `(i & 1)` in parentheses.
- Counting bits with string conversion, which is slow and allocates a string per number.
What interviewers look for
Mention the per-number loop first and say its cost, then point out the reuse: "every number is a smaller number with one more bit appended." That framing leads straight to the recurrence and shows you are thinking in terms of subproblems.
If you know the i & (i - 1) trick, offer it as a second recurrence. Interviewers like candidates who can explain why both work.
Follow-up questions
Can you write a recurrence based on powers of two?
Yes. Track the largest power of two p ≤ i. Then bits[i] = 1 + bits[i - p], since i is p plus a smaller remainder. Update p each time i reaches the next power of two.
How would you count the bits of a single 32-bit number quickly?
Clear the lowest set bit with x & (x - 1) until x is 0, which loops once per 1 bit. For constant time, use the parallel bit-count trick that adds bits in pairs, then nibbles, then bytes, or a hardware popcount instruction.
How would you find the total number of 1 bits from 0 to n without building the array?
Count by bit position. For bit k, the pattern repeats every 2^(k+1) numbers with 2^k ones per cycle, so add full cycles times 2^k plus the ones in the final partial cycle. That is O(log n).
Companies that ask Counting Bits
Counting Bits is tagged by 93 companies in our interview dataset. The score shows how often it comes up at each company.
- Neogen100%
- Stitch Fix100%
- Fastly97%
- Dish Network92%
- Stockx91%
- Ihs Markit90%
- Sandvine87%
- Novartis86%
- Appian84%
- Raytheon84%
- Surveymonkey83%
- Aveva83%
- Thales82%
- Thumbtack82%
- Mts81%
- Alphasense80%
- Smartthings80%
- Fico78%
- Cloud Software Group78%
- Getyourguide77%
- Bio Rad Laboratories76%
- Moderna73%
- Northrop Grumman73%
- Activecampaign73%
and 69 more.
Practice next
Get live help in the real interview
Working solutions in real time during your actual interview. Invisible to screensharing.
Start Free TrialNo credit card required