1.3) Counting Bits

Given a non-negative integer n, for every i (0 ≤ i ≤ n), calculate the number of 1’s in their binary representation and return an array.

Sample Input/Output:

Let’s consider a sample input:

n = 5

Expected Output:

[0, 1, 1, 2, 1, 2]

Explanation:
For the given input n = 5, the binary representations of numbers from 0 to 5 are [0, 1, 10, 11, 100, 101]. The count of 1’s in these binary representations is [0, 1, 1, 2, 1, 2].

Time and Space Complexity:

The time complexity of the solution will be O(n), where n is the input integer. We calculate the count of 1’s for each number once.

The space complexity will be O(n) to store the array of counts.

Counting Bits C++ Solution:

#include <iostream>
#include <vector>

using namespace std;

vector<int> countBits(int n) {
    vector<int> result(n + 1);

    for (int i = 1; i <= n; ++i) {
        // Count of 1's for a number 'i' is equal to count of 1's for 'i / 2'
        // plus 1 if 'i' is odd (since the last bit will be 1)
        result[i] = result[i / 2] + (i % 2);
    }

    return result;
}

int main() {
    int n = 5;

    vector<int> result = countBits(n);

    cout << "Count of 1's in binary representation for numbers 0 to " << n << ":\n";
    for (int i : result) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

In this implementation, we use dynamic programming to calculate the count of 1’s in the binary representation for numbers from 0 to n. We initialize an array result to store the counts. For each number i from 1 to n, we calculate the count of 1’s by using the property that the count of 1’s for a number i is equal to the count of 1’s for i / 2 plus 1 if i is odd.

The main function demonstrates the usage of the countBits function by calculating the counts of 1’s for numbers from 0 to n.

The output will be:

Count of 1's in binary representation for numbers 0 to 5:
0 1 1 2 1 2