Check if a given number is sparse or not
Write a function to check if a given number is Sparse or not.
A number is said to be a sparse number if in the binary representation of the number no two or more consecutive bits are set.
Example:
Input: x = 72
Output: true
Explanation: Binary representation of 72 is 01001000.
There are no two consecutive 1âs in binary representationInput: x = 12
Output: false
Explanation: Binary representation of 12 is 1100.
Third and fourth bits (from end) are set.
Naive Approach: The idea is to check the consecutive bits of the number until the number becomes 0.
C++
#include <iostream> using namespace std; // Function to check if the number // is sparse or not. 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 ; } // Driver Code int main() { int n = 100; if (isSparse(n)) { cout << "Sparse" ; } else { cout << "Not Sparse" ; } return 0; } |
Java
// "static void main" must be defined in a public class. public class GFG { // Function to check if the number // is sparse or not. 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 ; } public static void main(String[] args) { int n = 100 ; if (isSparse(n)) { System.out.println( "Sparse" ); } else { System.out.println( "Not Sparse" ); } } } // This code is contributed by garg28harsh. |
Python3
# Python Code to Check if a given # number is sparse or not def isSparse(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 # Driver code n = 100 if (isSparse(n)): print ( "Sparse" ) else : print ( "Not Sparse" ) # This code is contributed by karandeep1234 |
C#
// C# Code to Check if a given // number is sparse or not using System; public class GFG { // Function to check if the number // is sparse or not. static 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 ; } public static void Main( string [] args) { int n = 100; if (isSparse(n)) { Console.WriteLine( "Sparse" ); } else { Console.WriteLine( "Not Sparse" ); } } } // This code is contributed by karandeep1234 |
Javascript
// Function to check if the number // is sparse or not. function isSparse(n) { let prev; if (n == 1) return true ; while (n > 0) { prev = n & 1; n = n >> 1; let curr = n & 1; if (prev == curr && prev == 1) return false ; prev = curr; } return true ; } // Driver Code let n = 100; if (isSparse(n)) { console.log( "Sparse" ); } else { console.log( "Not Sparse" ); } // This code is contributed by garg28harsh. |
Not Sparse
Time Complexity: O(Log2n)
Auxiliary Space: O(1)
Efficient Approach: To solve the problem follow the below idea:
If we observe carefully, then we can notice that if we can use bitwise AND of the binary representation of the âgiven number, then itâs âright-shifted numberâ(i.e., half the given number) to figure out whether the number is sparse or not. The result of AND operator would be 0 if the number is sparse and non-zero if not sparse.
Below is the implementation of the above approach:
C++
// C++ program to check if n is sparse or not #include <bits/stdc++.h> using namespace std; // Return true if n is sparse, else false bool checkSparse( int n) { // n is not sparse if there is set // in AND of n and n/2 if (n & (n >> 1)) return false ; return true ; } // Driver code int main() { // Function call cout << checkSparse(72) << endl; cout << checkSparse(12) << endl; cout << checkSparse(2) << endl; cout << checkSparse(3) << endl; return 0; } |
Java
// JAVA Code to Check if a // given number is sparse or not import java.util.*; class GFG { // Return true if n is // sparse,else false static int checkSparse( int n) { // n is not sparse if there // is set in AND of n and n/2 if ((n & (n >> 1 )) >= 1 ) return 0 ; return 1 ; } // Driver code public static void main(String[] args) { // Function call System.out.println(checkSparse( 72 )); System.out.println(checkSparse( 12 )); System.out.println(checkSparse( 2 )); System.out.println(checkSparse( 3 )); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python program to check # if n is sparse or not # Return true if n is # sparse, else false def checkSparse(n): # n is not sparse if there is set # in AND of n and n/2 if (n & (n >> 1 )): return 0 return 1 # Driver code if __name__ = = "__main__" : # Function call print (checkSparse( 72 )) print (checkSparse( 12 )) print (checkSparse( 2 )) print (checkSparse( 30 )) # This code is contributed # by Anant Agarwal. |
C#
// C# Code to Check if a given // number is sparse or not using System; class GFG { // Return true if n is // sparse,else false static int checkSparse( int n) { // n is not sparse if there // is set in AND of n and n/2 if ((n & (n >> 1)) >= 1) return 0; return 1; } // Driver code public static void Main() { // Function call Console.WriteLine(checkSparse(72)); Console.WriteLine(checkSparse(12)); Console.WriteLine(checkSparse(2)); Console.WriteLine(checkSparse(3)); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to check if // n is sparse or not // Return true if n is sparse, // else false function checkSparse( $n ) { // n is not sparse if // there is set in AND // of n and n/2 if ( $n & ( $n >> 1)) return 0; return 1; } // Driver Code // Function call echo checkSparse(72), "\n" ; echo checkSparse(12), "\n" ; echo checkSparse(2), "\n" ; echo checkSparse(3), "\n" ; // This code is contributed by Ajit. ?> |
Javascript
<script> // Javascript program to check if n is sparse or not // Return true if n is sparse, else false function checkSparse(n) { // n is not sparse if there is set // in AND of n and n/2 if ((n & (n>>1)) > 0) return 0; return 1; } document.write(checkSparse(72) + "</br>" ); document.write(checkSparse(12) + "</br>" ); document.write(checkSparse(2) + "</br>" ); document.write(checkSparse(3) + "</br>" ); </script> |
1 0 1 0
Time Complexity: O(1)
Auxiliary Space: O(1)
Note: Instead of the right shift, we could have used the left shift also, but the left shift might lead to an overflow in some cases.
Contact Us