Number is Sparse or Not

Problem

Given a number N. The task is to check whether it is sparse or not. A number is said to be a sparse number if no two or more consecutive bits are set in the binary representation.

Examples:

Example 1:

Input: N = 2
Output: 1
Explanation: Binary Representation of 2 is 10, which is not having consecutive set bits. So, it is sparse number.

Example 2:

Input: N = 3
Output: 0
Explanation: Binary Representation of 3 is 11, which is having consecutive set bits in it. So, it is not a sparse number.

Your task:

The task is to complete the function checkSparse() that takes n as a parameter and returns 1 if the number is sparse else returns 0.

• Expected Time Complexity: $O(1)$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^6$

Solution

Python

def isSparse(self,n):
    if (n == 1):
        return True
    global prev
    while(n > 0):
        prev = n & 1
        n = n >> 1
        curr = n & 1
        if(prev == curr and prev == 1):
            return False
        prev = curr
    return True 

Java

public static boolean isSparse(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;
}

C++

bool isSparse(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;
}

C

bool isSparse(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;
}

• Time Complexity: $O(1)$
• Auxiliary Space: $O(1)$