Counting Bits Problem Explanation

In the Counting Bits problem, given an integer n, the task is to return an array where the i-th element is the number of 1’s in the binary representation of the integer i for all numbers from 0 to n.

Approach 1: Brute Force Method

We can solve this problem by iterating through each number from 0 to n, converting each number to its binary form, and counting the number of 1 bits.

Time Complexity:

• For each number i, we check its bits, which takes O(log i) time.
• Thus, the overall time complexity for this approach is O(n log n), because we are checking each number’s binary representation individually.

Code for Brute Force Method:

#include <stdio.h>
#include <stdlib.h>

int countOnes(int num) // O(Log n)
{
    int count = 0;
    while (num > 0)
    {
        count += num % 2;  // Check if the current least significant bit is 1
        num /= 2;           // Shift the number right to check the next bit
    }
    return count;
}

void countBits(int n, int ans[])
{
    for (int i = 0; i <= n; i++)
    {
        ans[i] = countOnes(i);  // Count 1's for each number from 0 to n
    }
}

int main()
{
    int n = 5;

    int ans[n + 1];
    countBits(n, ans);

    printf("Result: ");
    for (int i = 0; i <= n; i++)
    {
        printf("%d ", ans[i]);
    }
    printf("n");

    return 0;
}

Approach 2: Optimized Dynamic Programming Solution

We can solve the problem in O(n) time complexity using dynamic programming. The key observation here is that the number of 1 bits for any number i can be derived from the number of 1 bits for the number i / 2:

• For any number i, the number of 1 bits is the number of 1 bits in i / 2, plus 1 if i is odd (i.e., i % 2 == 1).

This can be done efficiently with the formula:

• ans[i] = ans[i / 2] + (i % 2)

This approach uses the previous results to build up the solution in linear time.

Time Complexity: O(n) because we are iterating through each number once and doing constant-time work for each.

Code for Optimized DP Method:

#include <stdio.h>
#include <stdlib.h>

void countBits(int n, int ans[])
{
    ans[0] = 0;  // Base case: number of 1's in binary representation of 0 is 0
    for (int i = 1; i <= n; i++)
    {
        ans[i] = ans[i / 2] + (i % 2);  // Use the relationship for the count of 1's
    }
}

int main()
{
    int n = 5;

    int ans[n + 1];
    countBits(n, ans);

    printf("Result: ");
    for (int i = 0; i <= n; i++)
    {
        printf("%d ", ans[i]);
    }
    printf("n");

    return 0;
}

Explanation of the Optimized Solution:

1. Base Case:
   ans[0] = 0, because the number of 1’s in the binary representation of 0 is 0.

2. Iterative Step:
   For each number i from 1 to n, we calculate ans[i] as:

   • ans[i] = ans[i / 2] + (i % 2)
     • i / 2 is the number obtained by shifting i right by one bit, and ans[i / 2] gives us the number of 1 bits in this number.
     • i % 2 adds 1 if i is odd (i.e., if i has a 1 in its least significant bit), otherwise adds 0.

3. Efficiency:
   This approach has a time complexity of O(n) because it only requires one pass through the array from 0 to n, and each operation is constant time.

Example:

For n = 5, the output will be:

Result: 0 1 1 2 1 2

This corresponds to the binary representations:

• 0 → 0 (0 ones)
• 1 → 1 (1 one)
• 2 → 10 (1 one)
• 3 → 11 (2 ones)
• 4 → 100 (1 one)
• 5 → 101 (2 ones)