Set-Bit Tally Table
EasyBit Manipulation
Problem
A lookup table speeds up a compression routine: entry i holds the number of 1 bits in the binary form of i.
Given n, return the table for every integer from 0 to n inclusive, as an array of length n + 1. Aim for a single linear pass rather than counting each number from scratch.
Example 1
- Input:
- n = 5
- Output:
- [0, 1, 1, 2, 1, 2]
0, 1, 10, 11, 100, 101 have 0, 1, 1, 2, 1, 2 set bits.
Example 2
- Input:
- n = 2
- Output:
- [0, 1, 1]
Constraints
- 0 ≤ n ≤ 10^5
Hint
Show the first hint
How does the binary form of i relate to the binary form of i >> 1?
Walkthrough
How to approach it
01Clarify before coding
- Is 0 included? Yes, the array has n + 1 entries starting with table[0] = 0.
- Can I use a built-in popcount? It works, but the point is to reuse earlier answers for O(n) total.
02Brute force
Run a popcount loop (clear the lowest set bit until zero) on every i from 0 to n.
Cost: O(n log n) time in the worst case, O(1) extra space beyond the output.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.