Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 338 with 13 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 338 # by problem number
lcpy gen -s counting_bits # by problem name
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.
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
O(n log n). Can you do it in linear time O(n) and possibly in a single pass?__builtin_popcount in C++)?class Solution:
def count_bits(self, n: int) -> list[int]:
"""
Optimized version with better variable naming and comments.
Time: O(n)
Space: O(1) excluding output array
"""
if n == 0:
return [0]
bits_count = [0] * (n + 1)
for num in range(1, n + 1):
# For any number, the count of 1s equals:
# count of 1s in (num >> 1) + whether the last bit is 1
bits_count[num] = bits_count[num >> 1] + (num & 1)
return bits_count
| Time | Space |
|---|---|
| - | - |