Problem Statement

Given a non-negative integer n, create an array ans of length n+1 where ans[i] represents the number of set bits in the binary representation of the integer 0≤i≤n.

Examples

Example 1:

Input: n = 5

Output: [0, 1, 1, 2, 1, 2]

Explanation:

• For n = 0, the number of set bits is 0.
• For n = 1, the number of set bits is 1.
• For n = 2, the number of set bits is 1.
• For n = 3, the number of set bits is 2.
• For n = 4, the number of set bits is 1.
• For n = 5, the number of set bits is 2.

So the array ans would be: [0, 1, 1, 2, 1, 2]

Different Approaches

1 Naive Recursion

Algorithm:

1. Base Case: If n is 0, return 0.
2. Recursive Step:
   1. Count the number of set bits in n/2.
   2. Add 1 to the count if n is odd.
3. Iterate: Calculate the number of set bits for each number from 0 to n using recursion.

Code Implementation in C++:

#include <iostream>
#include <vector>
using namespace std;

// Function to count the number of set bits in the binary representation of a number using recursion
int countSetBits(int n) {
    // Base case: if n is 0, return 0
    if (n == 0)
        return 0;
    
    // Recursive step: count set bits in n/2 and add 1 if n is odd
    return (n % 2) + countSetBits(n / 2);
}

vector<int> countBits(int n) {
    vector<int> ans;
    
    // Calculate the number of set bits for each number from 0 to n
    for (int i = 0; i <= n; i++) {
        ans.push_back(countSetBits(i));
    }
    
    return ans;
}

int main() {
    int n = 5;
    vector<int> result = countBits(n);
    
    cout << "Number of set bits for each number from 0 to " << n << " is:\n";
    for (int i = 0; i <= n; i++) {
        cout << i << ": " << result[i] << endl;
    }
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(n log n)
  • The recursive function runs O(log n) times for each number from 0 to n.
• Space Complexity:O(n)
  • We use an array of size n+1 to store the results.

2 Top-Down Approach (Memoization)

Code Implementation in C++:

#include <iostream>
#include <vector>
using namespace std;

int countSetBitsMemo(int n, vector<int>& memo) {
    // Base case: if n is 0, return 0
    if (n == 0)
        return 0;
    // If the result for n is already calculated, return it
    if (memo[n] != -1)
        return memo[n];
    // Recursive step: count set bits in n/2 and add 1 if n is odd
    memo[n] = (n % 2) + countSetBitsMemo(n / 2, memo);
    return memo[n];
}

vector<int> countBits(int n) {
    vector<int> memo(n + 1, -1); // Initialize memoization array with -1
    vector<int> ans(n + 1, 0);   // Initialize the result array with zeros
    // Calculate the number of set bits for each number from 0 to n
    for (int i = 0; i <= n; i++)
        ans[i] = countSetBitsMemo(i, memo);
    return ans;
}

int main() {
    int n = 5;
    vector<int> result = countBits(n);

    cout << "Number of set bits for each number from 0 to " << n << " is:\n";
    for (int i = 0; i <= n; i++) {
        cout << i << ": " << result[i] << endl;
    }

    return 0;
}