Given a non-negative integer num, create an array result of length num + 1 where each element result[i] represents the number of 1’s in the binary representation of i.

Function Signature:

from typing import List

def count_bits(num: int) -> List[int]:
    """
    Counts the number of 1's in the binary representation of each number from 0 to num.

    Parameters:
    - num: A non-negative integer.

    Returns:
    - List[int]: An array where each element represents the number of 1's in the binary representation.
    """
    # Your code here

Example:

num = 5
result = count_bits(num)
print(result)  # Output should be [0, 1, 1, 2, 1, 2]
# Explanation: 
# 0 has 0 bits set.
# 1 has 1 bit set.
# 2 has 1 bit set.
# 3 has 2 bits set.
# 4 has 1 bit set.
# 5 has 2 bits set.

Instructions:

  • Implement the count_bits function to solve the problem.
  • Use Python for your implementation.
  • Provide clear comments in your code to explain the logic.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊