Bitwise Operators: Check if the given number is sparse or not

Problem Statement:

You are given a number, you need to check if the number is sparse number or not.

A number is sparse if the binary representation of the number does not have no two or more consecutive bits are set.

Example:

Input 72
Output : True

Solution 1: Naive approach

Check the consecutive bits of the number until the number becomes 0

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

Solution 2: Efficient approach

Take bitwise AND of the binary of the number and do the right shift half of the given number.

If the result of AND operation is 0 then the number is sparse, else it is not sparse

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

Code Solution

#include <iostream>
using namespace std;

bool solution_1(int n)
{
    int prev;

    if (n == 1)
        return true;

    while (n > 0) 
    {
        prev = n & 1;
        n = n >> 1;
        int curr = n & 1;

        if (prev == curr && prev == 1)
            return false;

        prev = curr;
    }

    return true;
}

bool solution_2(int n)
{

    if (n & (n >> 1))
        return false;

    return true;
}
int main()
{

    int n = 100;
    if (solution_1(n)) 
    {
        cout << "Sparse";
    }
    else 
    {
        cout << "Not Sparse";
    }
    
    cout << "\n";

    if (solution_2(n)) 
    {
        cout << "Sparse";
    }
    else 
    {
        cout << "Not Sparse";
    }

    return 0;
}

Output

Not Sparse
Not Sparse