Recursion: Given a number, count the number of set bits using recursion

Problem Statement:

Given a number, count the number of set bits using recursion

Example:

Input: 21

Output: 3

Solution Explanation:

We will use recursion and right shift operator.

If num == 0, then return 0.

If LSB is set, then increase the count and then right shift, else only left shift.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

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

int solution(int n) 
{
    if (n == 0)
        return 0;

    if((n & 1) == 1)
        return 1 + solution(n >> 1);

    else
        return solution(n >> 1);
}

int main() 
{

	int n = 21;
	cout << solution(n) << endl;

	return 0;
}

Output

3