Counting Bits
Updated Jan 31, 2026
Problem
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.
Constraints
0 <= n <= 10^5
Follow Up
Can you do it in O(n) time and O(1) extra space (not counting the output)?
Examples
Example 1
Input:
n = 2
Output:
[0,1,1]
0 --> 0, 1 --> 1, 2 --> 10
Example 2
Input:
n = 5
Output:
[0,1,1,2,1,2]
0 --> 0, 1 --> 1, 2 --> 10, 3 --> 11, 4 --> 100, 5 --> 101
Function Signature
def countBits(self, n: int) -> list[int]
How to Submit
Implement a Solution class with a countBits method.
Your method will be called with the input parameters and should return the answer.