Check if a number is power of 8 or not
Given a number check whether it is a power of 8 or not.
Examples :
Input : n = 64 Output : Yes Input : 75 Output : No
First solution
We calculate log8(n) of the number if it is an integer, then n is in the power of 8. We use trunc(n) function that finds the closest integer for a double value.
C++
// C++ program to check if a number is power of 8 #include <cmath> #include <iostream> using namespace std; /* function to check if power of 8 */ bool checkPowerof8( int n) { /* calculate log8(n) */ double i = log (n) / log (8); /* check if i is an integer or not */ return (i - trunc(i) < 0.000001); } /* driver function */ int main() { int n = 65; checkPowerof8(n) ? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to check if // a number is power of 8 class GFG { // function to check // if power of 8 static boolean checkPowerof8( int n) { /* calculate log8(n) */ double i = Math.log(n) / Math.log( 8 ); /* check if i is an integer or not */ return (i - Math.floor(i) < 0.000001 ); } // Driver Code public static void main(String args[]) { int n = 65 ; if (checkPowerof8(n)) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Sam007 |
Python3
# Python3 program to check # if a number is power of 8 from math import log,trunc # function to check if power of 8 def checkPowerof8(n): # calculate log8(n) i = log(n, 8 ) # check if i is an integer or not return (i - trunc(i) < 0.000001 ); # Driver Code n = 65 if checkPowerof8(n): print ( "Yes" ) else : print ( "No" ) # This code is contributed by Mohit Kumar |
C#
// C# program to check if // a number is power of 8 using System; class GFG { // function to check // if power of 8 static bool checkPowerof8( int n) { // calculate log8(n) */ double i = Math.Log(n) / Math.Log(8); // check if i is an integer or not */ return (i - Math.Floor(i) < 0.000001); } // Driver Code static public void Main() { int n = 65; if (checkPowerof8(n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by akt_mit |
PHP
<?php // PHP program to check if // a number is power of 8 // function to check // if power of 8 function checkPowerof8( $n ) { /* calculate log8(n) */ $i = log( $n ) / log(8); /* check if i is an integer or not */ return ( $i - floor ( $i ) < 0.000001); } // Driver Code $n = 65; if (checkPowerof8( $n )) echo "Yes" ; else echo "No" ; // This code is contributed // by Sach_Code ?> |
Javascript
<script> // Javascript program to check if // a number is power of 8 // function to check // if power of 8 function checkPowerof8(n) { // calculate log8(n) */ let i = Math.log(n) / Math.log(8); // check if i is an integer or not */ return (i - Math.floor(i) < 0.000001); } let n = 65; if (checkPowerof8(n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output :
No
Time Complexity: O(1)
Auxiliary Space: O(1)
Second solution
A number is a power of 8 if the following conditions are satisfied.
- The number is the power of two. A number is the power of two if it has only one set bit, i.e., bitwise and of n and n-1 is 0.
- The number has its only set a bit at position 0 or 3 or 6 or …. 30 [For a 32-bit number]. To check the position of its set bit we can use a mask (0xB6DB6DB6)16 = (10110110110110110110110110110110)2.
Below is the implementation of the above idea.
C++
// C++ program to check if a number is power of 8 // using bit mask. #include <bits/stdc++.h> using namespace std; /*function to check if power of 8*/ bool checkPowerof8( int n) { return (n && !(n & (n - 1)) && !(n & 0xB6DB6DB6)); } /*driver function*/ int main() { int n = 65; checkPowerof8(n) ? cout << "Yes" : cout << "No" ; return 0; } |
Java
// Java program to check if a // number is power of 8 using // bit mask. import java.util.*; class GFG{ // function to check if // power of 8 static boolean checkPowerof8( int n) { return (n > 0 && (n & (n - 1 )) > 0 && (n & 0xB6DB6DB6 ) > 0 ); } // Driver code public static void main(String[] args) { int n = 65 ; if (checkPowerof8(n) == true ) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to check if a number # is power of 8 # function to check if power of 8 def checkPowerof8(n): return (n and not (n & (n - 1 )) and not (n & 0xB6DB6DB6 )) # Driver Code if __name__ = = "__main__" : n = 65 if checkPowerof8(n): print ( "Yes" ) else : print ( "No" ) # This code is contributed by ita_c |
C#
// C# program to check if a // number is power of 8 using // bit mask. using System; class GFG{ // Function to check if // power of 8 static bool checkPowerof8( int n) { return (n > 0 && (n & (n - 1)) > 0 && (n & 0xB6DB6DB6) > 0); } // Driver code static public void Main() { int n = 65; if (checkPowerof8(n) == true ) { Console.WriteLine( "Yes" ); } else { Console.WriteLine( "No" ); } } } // This code is contributed by avanitrachhadiya2155 |
PHP
<?php // PHP program to check if a number // is power of 8 using bit mask. // function to check if power of 8 function checkPowerof8( $n ) { $t = ( $n && !( $n & ( $n - 1)) && !( $n & 0xB6DB6DB6)); return $t ; } // Driver Code $n = 65; if (checkPowerof8( $n )) echo "Yes" ; else echo "No" ; // This code is contributed by Sach ?> |
Javascript
<script> /*function to check if power of 8*/ function checkPowerof8( n) { return (n && !(n & (n - 1)) && !(n & 0xB6DB6DB6)); } var n = 65; if (checkPowerof8(n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output :
No
Time Complexity: O(1)
Auxiliary Space: O(1)
One simple observation that can be made here is that if a number is the power of 8 then it has only a one-bit set and that bit is at positions 1, 4, 7, 10, …
Thus, we can just check if the only bit set in the number is at one of these positions then it is a power of 8 otherwise not.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to check if n is power of 8 bool checkPowerof8( int n) { // Variable i will denote the bit // that we are currently at int i = 0; unsigned long long l = 1; while (i <= 63) { l <<= i; // If only set bit in n // is at position i if (l == n) return true ; // Get to next valid bit position i += 3; l = 1; } return false ; } // Driver code int main() { int n = 65; if (checkPowerof8(n)) cout << "Yes" ; else cout << "No" ; return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to check if n is power of 8 static boolean checkPowerof8( int n) { // Variable i will denote the bit // that we are currently at int i = 0 ; long l = 1 ; while (i <= 63 ) { l <<= i; // If only set bit in n // is at position i if (l == n) return true ; // Get to next valid bit position i += 3 ; l = 1 ; } return false ; } // Driver code public static void main (String[] args) { int n = 65 ; if (checkPowerof8(n)) System.out.println ( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Tushil. |
Python3
# Python3 implementation of the approach # Function to check if n is power of 8 def checkPowerof8(n): # Variable i will denote the bit # that we are currently at i = 0 l = 1 while (i < = 63 ): l << = i # If only set bit in n # is at position i if (l = = n): return True # Get to next valid bit position i + = 3 l = 1 return False # Driver code if __name__ = = '__main__' : n = 65 if (checkPowerof8(n)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by math_lover |
C#
// C# implementation of the approach using System; class GFG { // Function to check if n is power of 8 static bool checkPowerof8( int n) { // Variable i will denote the bit // that we are currently at int i = 0; long l = 1; while (i <= 63) { l <<= i; // If only set bit in n // is at position i if (l == n) return true ; // Get to next valid bit position i += 3; l = 1; } return false ; } // Driver code static public void Main () { int n = 65; if (checkPowerof8(n)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by ajit. |
Javascript
<script> // Function to check if n is power of 8 function checkPowerof8( n) { // Variable i will denote the bit // that we are currently at var i = 0; var l= 1; while (i <= 63) { l<<=i; // If only set bit in n // is at position i if (l == n) return 1; // Get to next valid bit position i += 3; l = 1; } return 0; } var n = 65; if (checkPowerof8(n)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output :
No
Time Complexity: O(1)
Auxiliary Space: O(1)