Bit Manipulation
12. Counting Bits
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Examples
Example 1
Input: n = 2
Output: [0,1,1]
Explanation:
0 -> 0
1 -> 1
2 -> 10
Example 2
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 -> 0
1 -> 1
2 -> 10
3 -> 11
4 -> 100
5 -> 101
Constraints
0 <= n <= 10^5
Follow-up
- A straightforward solution runs in O(n log n); try to achieve O(n) time and O(n) space.
- You can compute counts in O(1) per number using dynamic programming relations such as
ans[i] = ans[i >> 1] + (i & 1)orans[i] = ans[i & (i - 1)] + 1. - Avoid using built-in population-count functions for the challenge.
from typing import List
# Count the number of 1-bits for every number from 0 to n
n: int = 5
dp: List[int] = [0] * (n + 1)
offset: int = 1
for i in range(1, n + 1):
if offset * 2 == i:
offset = i
dp[i] = 1 + dp[i - offset]
print(dp)Keyboard shortcuts
← h Previous problem
→ l Next problem
Esc Back to index
? Toggle this help