288. Bit Count Table
A hardware team wants a lookup table that tells, for every control word from 0 up to a limit, how many of its binary digits are 1. They will query the table millions of times, so it must be built in a single pass rather than by counting bits separately for every entry.
Given the integer n, return an array ans of length n + 1 where ans[i] is the number of 1 bits in the binary representation of i, for every i from 0 to n. For example with n = 9 the answer is [0,1,1,2,1,2,2,3,1,2]. Reuse results of smaller numbers so the total time is linear in n, with no per-number loop over the bits.
Example 1
- Input:
- n = 9
- Output:
- [0,1,1,2,1,2,2,3,1,2]
- Explanation:
Index by index the set-bit counts are 0,1,1,2,1,2,2,3,1,2 for the numbers 0 through 9.
Example 2
- Input:
- n = 0
- Output:
- [0]
- Explanation:
Only the number 0 is requested, and it has no set bits.
Example 3
- Input:
- n = 16
- Output:
- [0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1]
- Explanation:
Numbers 8..15 add one to the counts of 0..7, and 16 is a single bit again.
Constraints
0 ≤ n ≤ 2500
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(n)