PROBLEM DESCRIPTION
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.
SOLUTION
APPROACH 1
We can solve this by iterating through the binary representation of the given number and checking if any two consecutive bits are set. Starting from the least significant bit, we track whether the current bit is 1 using a boolean variable. With each iteration, we right shift the number to examine the next bit. If at any point two consecutive 1s are found, we immediately return false since the number is not sparse.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution
{
public static boolean isSparse(int n)
{
// Initially check if the least significant bit (LSB) is set (1).
boolean set = ((n & 1) != 0);
// Right shift the number by 1 to examine the next bit.
n = n >> 1;
// Continue checking each bit of the number.
while(n != 0) {
// If the current bit is set (1) and the previous bit was also set (i.e., two consecutive bits are set).
if (((n & 1) != 0) && set == true) {
// Return false because the number is not sparse (two consecutive set bits found).
return false;
}
// Update the 'set' variable to check the next bit in the next iteration.
set = ((n & 1) != 0);
// Right shift the number again to move to the next bit.
n = n >> 1;
}
// If no two consecutive set bits are found, the number is sparse, return true.
return true;
}
}
APPROACH 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution
{
//Function to check if the number is sparse or not.
public static boolean isSparse(int n)
{
//we perform Right shift on n by 1 bit.
//then perform AND operation on n and n/2
//(obtained by right shifting n by 1 bit).
//returning true if we get 0 as result otherwise false.
return (n & (n >> 1)) == 0;
}
}