Check if given number is a power of d where d is a power of 2
Given an integer n, find whether it is a power of d or not, where d is itself a power of 2.
Examples:
Input : n = 256, d = 16 Output : Yes Input : n = 32, d = 16 Output : No
Method 1 Take log of the given number on base d, and if we get an integer then number is power of d.
C++
// CPP program to find if a number is power // of d where d is power of 2. #include<bits/stdc++.h> bool isPowerOfd( int n, int d) { //Take log of the given number on base d, //and if we get an integer then number is power of d. return (( int )( log (n) / log (d)) == ( int ) log (n) / ( int ) log (d)); } /* Driver program to test above function*/ int main() { int n = 64, d = 8; if (isPowerOfd(n, d)) printf ( "%d is a power of %d" , n, d); else printf ( "%d is not a power of %d" , n, d); return 0; } |
Python3
#Python3 program to find if a number is power # of d where d is power of 2. from math import log def isPowerOfd(n, d): #Take log of the given number on base d, #and if we get an integer then number is power of d. return log(n) / log(d) = = log(n) / / log(d) # Driver program to test above function* n = 64 d = 8 if (isPowerOfd(n, d)): print (n, "is a power of" , d) else : print (n, "is not a power of" , d) #This code is contributed by phasing17 |
Java
public class Main { public static boolean isPowerOfd( int n, int d) { //Take log of the given number on base d, //and if we get an integer then number is power of d. return (Math.log(n) / Math.log(d) == ( int ) (Math.log(n) / Math.log(d))); } public static void main(String[] args) { int n = 64 , d = 8 ; if (isPowerOfd(n, d)) System.out.println(n + " is a power of " + d); else System.out.println(n + " is not a power of " + d); } } |
C#
using System; public class Mainn { public static bool IsPowerOfd( int n, int d) { //Take log of the given number on base d, //and if we get an integer then number is power of d. return (Math.Log(n) / Math.Log(d) == ( int ) (Math.Log(n) / Math.Log(d))); } public static void Main( string [] args) { int n = 64, d = 8; if (IsPowerOfd(n, d)) Console.WriteLine(n + " is a power of " + d); else Console.WriteLine(n + " is not a power of " + d); } } |
Javascript
// JavaScript program to find if a number is power // of d where d is power of 2. function isPowerOfd(n, d) { //Take log of the given number on base d, //and if we get an integer then number is power of d. return (Math.floor((Math.log(n) / Math.log(d)))) == (Math.log(n) /Math.log(d)); } /* Driver program to test above function*/ let n = 64, d = 8; if (isPowerOfd(n, d)) console.log(n + " is a power of " + d); else console.log(n + " is not a power of " + d); //This code is contributed by phasing17 |
64 is a power of 8
Method 2 Keep dividing the number by d, i.e, do n = n/d iteratively. In any iteration, if n%d becomes non-zero and n is not 1 then n is not a power of d, otherwise n is a power of d.
Method 3(Bitwise)
A number n is a power of d if following conditions are met.
a) There is only one bit set in the binary representation of n (Note : d is a power of 2)
b) The count of zero bits before the (only) set bit is a multiple of log2(d).
For example: For n = 16 (10000) and d = 4, 16 is a power of 4 because there is only one bit set and count of 0s before the set bit is 4 which is a multiple of log2(4).
Steps to solve this problem:
1. declare variable count=0.
2. check if n&&!(n&(n-1)) is true than :
*while n is greater than 1:
*n>>=1.
*update count to count+1.
*return count%(log2n(d))==0.
3. return false.
C++
// CPP program to find if a number is power // of d where d is power of 2. #include<stdio.h> unsigned int Log2n(unsigned int n) { return (n > 1)? 1 + Log2n(n/2): 0; } bool isPowerOfd(unsigned int n, unsigned int d) { int count = 0; /* Check if there is only one bit set in n*/ if (n && !(n&(n-1)) ) { /* count 0 bits before set bit */ while (n > 1) { n >>= 1; count += 1; } /* If count is a multiple of log2(d) then return true else false*/ return (count%(Log2n(d)) == 0); } /* If there are more than 1 bit set then n is not a power of 4*/ return false ; } /* Driver program to test above function*/ int main() { int n = 64, d = 8; if (isPowerOfd(n, d)) printf ( "%d is a power of %d" , n, d); else printf ( "%d is not a power of %d" , n, d); return 0; } |
Java
// Java program to find if // a number is power of d // where d is power of 2. class GFG { static int Log2n( int n) { return (n > 1 )? 1 + Log2n(n / 2 ): 0 ; } static boolean isPowerOfd( int n, int d) { int count = 0 ; /* Check if there is only one bit set in n*/ if (n > 0 && (n & (n - 1 )) == 0 ) { /* count 0 bits before set bit */ while (n > 1 ) { n >>= 1 ; count += 1 ; } /* If count is a multiple of log2(d) then return true else false*/ return (count % (Log2n(d)) == 0 ); } /* If there are more than 1 bit set then n is not a power of 4*/ return false ; } // Driver Code public static void main(String[] args) { int n = 64 , d = 8 ; if (isPowerOfd(n, d)) System.out.println(n + " is a power of " + d); else System.out.println(n + " is not a power of " + d); } } // This code is contributed by mits |
Python3
# Python3 program to find if a number # is power of d where d is power of 2. def Log2n(n): return ( 1 + Log2n(n / 2 )) if (n > 1 ) else 0 ; def isPowerOfd(n, d): count = 0 ; # Check if there is only # one bit set in n if (n and (n & (n - 1 )) = = 0 ): # count 0 bits # before set bit while (n > 1 ): n >> = 1 ; count + = 1 ; # If count is a multiple of log2(d) # then return true else false return (count % (Log2n(d)) = = 0 ); # If there are more than 1 bit set # then n is not a power of 4 return False ; # Driver Code n = 64 ; d = 8 ; if (isPowerOfd(n, d)): print (n, "is a power of" ,d); else : print (n, "is not a power of" ,d); # This code is contributed by mits |
C#
// C# program to find if // a number is power of d // where d is power of 2. using System; class GFG { static int Log2n( int n) { return (n > 1)? 1 + Log2n(n / 2): 0; } static bool isPowerOfd( int n, int d) { int count = 0; /* Check if there is only one bit set in n*/ if (n > 0 && (n & (n - 1)) == 0) { /* count 0 bits before set bit */ while (n > 1) { n >>= 1; count += 1; } /* If count is a multiple of log2(d) then return true else false*/ return (count % (Log2n(d)) == 0); } /* If there are more than 1 bit set then n is not a power of 4*/ return false ; } // Driver Code static void Main() { int n = 64, d = 8; if (isPowerOfd(n, d)) Console.WriteLine( "{0} is a " + "power of {1}" , n, d); else Console.WriteLine( "{0} is not a" + " power of {1}" , n, d); } // This code is contributed by mits } |
PHP
<?php // PHP program to find if a number // is power of d where d is power of 2. function Log2n( $n ) { return ( $n > 1)? 1 + Log2n( $n / 2): 0; } function isPowerOfd( $n , $d ) { $count = 0; // Check if there is only // one bit set in n if ( $n && !( $n & ( $n - 1))) { // count 0 bits // before set bit while ( $n > 1) { $n >>= 1; $count += 1; } /* If count is a multiple of log2(d) then return true else false*/ return ( $count %(Log2n( $d )) == 0); } /* If there are more than 1 bit set then n is not a power of 4*/ return false; } // Driver Code $n = 64; $d = 8; if (isPowerOfd( $n , $d )) echo $n , " " , "is a power of " , $d ; else echo $n , " " , "is not a power of " , $d ; // This code is contributed by m_kit ?> |
Javascript
<script> // Javascript program to find if // a number is power of d // where d is power of 2 function Log2n(n) { return (n > 1) ? 1 + Log2n(n / 2) : 0; } // Function to count the number // of ways to paint N * 3 grid // based on given conditions function isPowerOfd(n, d) { var count = 0; /* Check if there is only one bit set in n*/ if (n > 0 && (n & (n - 1)) == 0) { /* count 0 bits before set bit */ while (n > 1) { n >>= 1; count += 1; } /* If count is a multiple of log2(d) then return true else false*/ return (count % (Log2n(d)) == 0); } /* If there are more than 1 bit set then n is not a power of 4*/ return false ; } // Driver code var n = 64, d = 8; if (isPowerOfd(n, d)) document.write(n + " is a power of " + d); else document.write(n + " is not a power of " + d); // This code is contributed by Khushboogoyal499 </script> |
64 is a power of 8
Time Complexity: O(log2n)
Auxiliary Space: O(1)