Counting Bits
Easy · Bit Manipulation · Dynamic Programming · Bit Manipulation
Problem
Given an integer n, return an array of length n + 1 where position i holds the number of 1 bits in i.
Examples
Input: n = 2 Output: [0,1,1]
0, 1, 10 in binary.
Input: n = 5 Output: [0,1,1,2,1,2]
Constraints
- 0 <= n <= 10^5
Approaches
- Reuse the answer for i >> 1 — time O(n), space O(1) extra
Follow-up
Counting bits for each number separately takes O(n log n). Can you produce the answer in a single O(n) pass without using a built-in popcount?
Related problems
Start free on Cariara · Coding problems · System design studio
