Counting Bits
Problem Statement
Given an integer n
, count the number of 1
’s in the binary representation of every number in the range [0, n]
.
Return an array output
where output[i]
is the number of 1
’s in the binary representation of i
.
Example 1:
# Input: n = 4# Output: [0,1,1,2,1]n = 4output = [0, 1, 1, 2, 1]print(output)
Explanation: 0 —> 0 1 —> 1 2 —> 10 3 —> 11 4 —> 100
Constraints:
0 <= n <= 1000
Recommended Time and Space Complexity
You should aim for a solution with O(n)
time and O(n)
space, where n
is the input number.
Solution
Bit Manipulation - I
def count_bits_bit_manipulation_i(n: int) -> List[int]: res = [] for num in range(n + 1): one = 0 for i in range(32): if num & (1 << i): one += 1 res.append(one) return res
Time complexity: O(n)
Space complexity: O(1)