Sparse Numbers in Java

In this section, we will be very well acknowledged about the sparse numbers in Java, how a number can be verified if it is a sparse number or not.

Sparse Numbers

Any number with binary representation lacks two or more continuous set bits is said to be sparse number.

Let us discuss some examples to be clear about the sparse numbers.

Example1:

Consider an integer n

n = 17

The binary equivalent representation of 17 is 10001.

In the binary representation, the 1’s are not consecutive. Thus 17 is a sparse number.

Example2:

Now consider n = 19

The binary equivalent representation of 19 is 10011.

In the binary representation, the 1’s are consecutive. Thus 19 is not a sparse number.

Example3:

Consider n= 25

The binary equivalent representation of 25 is 11001.

In the binary representation, the 1’s are consecutive. Thus 25 is not a sparse number.

For an integer to know if it is a sparse number or not, we must know the binary number equivalent to the given integer.

So let us first learn to find out the binary equivalent number to the given number.

File name: Binary.java

// Conversion of decimal number to binary number
import java.io.*;
import java.util.*;
class Binary {
static int decimalToBinary(int N)
{


int B_Number = 0;
int cnt = 0;
while (N != 0) {
int rem = N % 2;
double c = Math.pow(10, cnt);
B_Number += rem * c;
N /= 2;
cnt++;
}


return B_Number;
}
public static void main(String[] args)
{
Scanner s= new Scanner(System.in);
int N = s.nextInt();;
System.out.println("Decimal - " + N);
System.out.print("Binary - ");
System.out.println(decimalToBinary(N));
}
}

Output

Decimal - 6
Binary - 110
Decimal - 63
Binary – 111111

Now let us understand the process of verifying if a number is a sparse number. For that there are certain approaches that must be followed.

Approach

• Using an ArrayList
• Using Right Shift Operators

Using an ArrayList

The binary equivalent of the number can be stored in an array list, which can then be traversed to determine whether the two next elements in the array list possess 1 or not. The provided number will not be a sparse number if it consists two consecutive ones. Else, it is.

Let us look at the below program to understand.

File name: Sparse1.java

import java.util.ArrayList;  
  
public class Sparse1  
{  
  
// a technique that determines whether or not the integer n is indeed a sparse number
public boolean isSparseNum(int n)  
{  
ArrayList<Integer> al = new ArrayList<Integer>();  
while(n != 0)  
{  
    al.add(n % 2);  
    n = n / 2;  
}  
  
int size = al.size();  
for(int i = 0; i < size - 1; i++)  
{  
    // determining whether or not the two successive items are 1
    if((al.get(i) == al.get(i + 1)) && (al.get(i) == 1))  
    {  
        return false;  
    }  
}  
  
return true;  
  
}  
  public static void main(String[] argvs)  
{  
Sparse1 obj = new Sparse1();  
  
int range = 25;  
  
System.out.println("The Spare numbers lying between 1 to " + range + " are: ");  
  
for(int i = 1; i <= range; i++)  
{  
    if(obj.isSparseNum(i))  
    {  
        System.out.print(i + " ");  
    }  
}  
  
}  
}  

Output

The Sparse numbers between 1 to 25 are:
1 2 4 5 8 9 10 16 17 18 20 21

Using Right Shift Operator

To compute the sparse number, we can utilize the right shift operator. We will use this attribute to estimate the sparse number because we are aware that two subsequent bits cannot be set. If we pay close attention, we will see that determining whether a number seems to be sparse or not requires using the bitwise AND of both binary equivalent of the "provided number" and the "right-shifted number" (i.e., half the supplied number). If a number is sparse, the AND operator's output would be 0, and if it is not sparse, it would be non-zero.

File name: Sparse2.java

// Java code to determine whether or not a specific number is sparse
import java.util.*;
class Sparse2 {
// Returns true if it a sparse number else false
static int checkSparse(int n)
{
if ((n & (n >> 1)) >= 1)
return 0;
                                        return 1;
}
public static void main(String[] args)
{
System.out.println(checkSparse(19));
System.out.println(checkSparse(56));
System.out.println(checkSparse(17));
System.out.println(checkSparse(30));
}
}

Output

0
0
1
0