Problem Statement

Given a number N, find the number of set bits in its binary representation using recursion.

Examples

Example 1:

Input: 7
Output: 3

Explanation: 7 is represented as 0111 in binary representation, so total set bits are 3.

Different Approaches

1️⃣ Approach: Using Shift Operator

Algorithm:

1. First, check the LSB of the number.
2. If the LSB is 1, then we add 1 to our answer and divide the number by 2.
3. If the LSB is 0, we add 0 to our answer and divide the number by 2.
4. Then we recursively follow step (1) until the number is greater than 0.

Code Implementation in C++:

#include <bits/stdc++.h>
using namespace std;
 
// Recursive function to find 
// number of set bist in a number
int CountSetBits(int n)
{
    // Base condition
    if (n == 0)
        return 0;
         
    // If Least significant bit is set
    if((n & 1) == 1)
        return 1 + CountSetBits(n >> 1);
     
    // If Least significant bit is not set
    else
        return CountSetBits(n >> 1);
}
 
int main()
{
    int n = 21;
     
    // Function call
    cout << CountSetBits(n) << endl;
 
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log n)
• Space Complexity:O(log n)

2️⃣ Approach: Using Division Method

Code Implementation in C++:

#include <iostream>
using namespace std;

// Function to count the total number of set bits in 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
    int setBits = countSetBits(n / 2);
    
    // Combine: set bits in n is equal to n % 2 plus set bits in n/2
    return (n % 2) + setBits;
}

int main() {
    int n = 10;
    cout << "Total set bits in " << n << ": " << countSetBits(n) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log n)
  • At each step, we divide the number by 2.
• Space Complexity:O(log n)