Counting Bits easy

Problem Statement

Given an integer 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.

Example 1:

Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10

Example 2:

Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101

Steps:

1. Initialization: Create an array ans of size n + 1 and initialize the first element ans[0] to 0 (since the binary representation of 0 has zero 1s).

2. Iteration: Iterate from i = 1 to n. For each i:

   • Determine the number of 1s in the binary representation of i. We can do this using bit manipulation or string conversion. The most efficient method uses bit manipulation.
   • Store the count of 1s in ans[i].

3. Optimized Approach (using dynamic programming): We can optimize this further by observing a pattern. The number of 1s in i is related to the number of 1s in i/2 (integer division). If i is even, the number of 1s is the same as i/2. If i is odd, the number of 1s is one more than the number of 1s in i/2. This allows us to build up the solution iteratively.

Explanation:

The dynamic programming approach leverages the relationship between the number of set bits in a number and its preceding numbers. If a number is even, its binary representation is the same as its half, but with an extra 0 at the end. Thus, the count of set bits remains the same. If a number is odd, it's the same as its half, but with an extra 1 at the end. Thus, the count of set bits increments by 1. This relationship allows us to build the solution iteratively, avoiding the repeated counting of set bits for each number.

Code:

def countBits(n: int) -> list[int]:
    """
    Counts the number of 1s in the binary representation of each integer from 0 to n.

    Args:
        n: The upper limit of the range (inclusive).

    Returns:
        A list containing the number of 1s for each integer from 0 to n.
    """
    ans = [0] * (n + 1)  # Initialize the result array
    for i in range(1, n + 1):
        ans[i] = ans[i >> 1] + (i & 1)  # Optimized DP approach
    return ans

Complexity:

• Time Complexity: O(n) - We iterate through the numbers from 1 to n once. The bitwise operations (>> and &) are constant time.

• Space Complexity: O(n) - We use an array of size n+1 to store the results.