Solution 1: Brute Force

Intuition:

A brute force approach to count the number of set bits in each number from 0 to num would involve directly counting the set bits for each number individually without utilizing any precomputed values or optimization techniques. This approach would iterate over each bit in each number and count the number of set bits using bitwise operations.

Solution:

from typing import List

def count_bits(num: int) -> List[int]:
    result = []
    for i in range(num + 1):
    	# Initialize a count variable to store the number of set bits
        count = 0
        # Iterate over each bit in the binary representation of i 
        n = i
        while n:
        	# Increment the count if the bit is set (i.e., equal to 1)
            count += n & 1
            n >>= 1
        # After iterating over all the bits, 
        # append the count to the result array for the current number i
        result.append(count)
    return result

# Test case
num = 5
result = count_bits(num)
print(result)  # Output should be [0, 1, 1, 2, 1, 2]

Time Complexity:

  • Since the value of num itself can be represented using log(max_value) bits, where max_value is the maximum value of num in the input, we perform log(max_value) operations to count the number of set bits for each number i from 0 to num.
  • The time complexity of this brute force approach is O(num * log(max_value)).

Space Complexity:

  • The space complexity is O(num) since we store the result array of length num + 1.
  • Additionally, the space complexity is O(1) for other variables used in the function.

Solution 2: Dynamic Programming

Intuition:

To count the number of 1’s in the binary representation of each number from 0 to num, we can also utilize dynamic programming. We observe that the number of 1’s in the binary representation of a number i is equal to the number of 1’s in the binary representation of i // 2, plus 1 if i is odd. This observation forms the basis of our dynamic programming approach, where we build the result array iteratively based on previous calculations.

Solution:

from typing import List

def count_bits(num: int) -> List[int]:
    # Initialize the result array with 0's
    result = [0] * (num + 1)
    # Iterate from 1 to num
    for i in range(1, num + 1):
        # Number of 1's in the binary representation of i equals:
        # - Number of 1's in the binary representation of i // 2 if i is even
        # - Number of 1's in the binary representation of i // 2 plus 1 if i is odd
        result[i] = result[i // 2] + (i % 2)
    return result

# Test case
num = 5
result = count_bits(num)
print(result)  # Output should be [0, 1, 1, 2, 1, 2]

Time Complexity:

  • We iterate from 1 to num, performing constant-time operations for each iteration.
  • The time complexity of this approach is O(num), where num is the input integer.

Space Complexity:

  • The space complexity is O(num) since we store the result array of length num + 1.
  • Additionally, the space complexity is O(1) for other variables used in the function.