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 = 4
output = [0, 1, 1, 2, 1]
print(output)

Explanation: 0 —> 0 1 —> 1 2 —> 10 3 —> 11 4 —> 100

Constraints:

  • 0 <= n <= 1000

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)