Check if a number is power of k using base changing method
This program checks whether a number n can be expressed as power of k and if yes, then to what power should k be raised to make it n. Following example will clarify :
Examples:
Input : n = 16, k = 2 Output : yes : 4 Explanation : Answer is yes because 16 can be expressed as power of 2. Input : n = 27, k = 3 Output : yes : 3 Explanation : Answer is yes as 27 can be expressed as power of 3. Input : n = 20, k = 5 Output : No Explanation : Answer is No as 20 cannot be expressed as power of 5.
We have discussed two methods in below post
:Check if a number is a power of another number
In this post, a new Base Changing method is discussed.
In Base Changing Method, we simply change the base of number n to k and check if the first digit of Changed number is 1 and remaining all are zero.
Example for this : Let’s take n = 16 and k = 2.
Change 16 to base 2. i.e. (10000)2. Since first digit is 1 and remaining are zero. Hence 16 can be expressed as power of 2. Count the length of (10000)2 and subtract 1 from it, that’ll be the number to which 2 must be raised to make 16. In this case 5 – 1 = 4.
Another example : Let’s take n = 20 and k = 3.
20 in base 3 is (202)3. Since there are two non-zero digit, hence 20 cannot be expressed as power of 3.
C++
// CPP program to check if a number can be // raised to k #include <iostream> #include <algorithm> using namespace std; bool isPowerOfK(unsigned int n, unsigned int k) { // loop to change base n to base = k bool oneSeen = false ; while (n > 0) { // Find current digit in base k int digit = n % k; // If digit is neither 0 nor 1 if (digit > 1) return false ; // Make sure that only one 1 // is present. if (digit == 1) { if (oneSeen) return false ; oneSeen = true ; } n /= k; } return true ; } // Driver code int main() { int n = 64, k = 4; if (isPowerOfK(n ,k)) cout << "Yes" ; else cout << "No" ; } |
Java
// Java program to check if a number can be // raised to k class GFG { static boolean isPowerOfK( int n, int k) { // loop to change base n to base = k boolean oneSeen = false ; while (n > 0 ) { // Find current digit in base k int digit = n % k; // If digit is neither 0 nor 1 if (digit > 1 ) return false ; // Make sure that only one 1 // is present. if (digit == 1 ) { if (oneSeen) return false ; oneSeen = true ; } n /= k; } return true ; } // Driver code public static void main (String[] args) { int n = 64 , k = 4 ; if (isPowerOfK(n ,k)) System.out.print( "Yes" ); else System.out.print( "No" ); } } // This code is contributed by Anant Agarwal. |
Python3
# Python program to # check if a number can be # raised to k def isPowerOfK(n, k): # loop to change base # n to base = k oneSeen = False while (n > 0 ): # Find current digit in base k digit = n % k # If digit is neither 0 nor 1 if (digit > 1 ): return False # Make sure that only one 1 # is present. if (digit = = 1 ): if (oneSeen): return False oneSeen = True n / / = k return True # Driver code n = 64 k = 4 if (isPowerOfK(n , k)): print ( "Yes" ) else : print ( "No" ) # This code is contributed # by Anant Agarwal. |
C#
// C# program to check if a number can be // raised to k using System; class GFG { static bool isPowerOfK( int n, int k) { // loop to change base n to base = k bool oneSeen = false ; while (n > 0) { // Find current digit in base k int digit = n % k; // If digit is neither 0 nor 1 if (digit > 1) return false ; // Make sure that only one 1 // is present. if (digit == 1) { if (oneSeen) return false ; oneSeen = true ; } n /= k; } return true ; } // Driver code public static void Main () { int n = 64, k = 4; if (isPowerOfK(n ,k)) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to check // if a number can be // raised to k function isPowerOfK( $n , $k ) { // loop to change base // n to base = k $oneSeen = false; while ( $n > 0) { // Find current // digit in base k $digit = $n % $k ; // If digit is // neither 0 nor 1 if ( $digit > 1) return false; // Make sure that // only one 1 // is present. if ( $digit == 1) { if ( $oneSeen ) return false; $oneSeen = true; } $n = (int) $n / $k ; } return true; } // Driver code $n = 64; $k = 4; if (isPowerOfK( $n , $k )) echo "Yes" ; else echo "No" ; // This code is contributed // by ajit ?> |
Javascript
<script> // JavaScript program to check if a number can be // raised to k function isPowerOfK(n,k) { // loop to change base n to base = k let oneSeen = false ; while (n > 0) { // Find current digit in base k let digit = n % k; // If digit is neither 0 nor 1 if (digit > 1) return false ; // Make sure that only one 1 // is present. if (digit == 1) { if (oneSeen) return false ; oneSeen = true ; } n = Math.floor(n / k); } return true ; } // Driver Code let n = 64, k = 4; if (isPowerOfK(n ,k)) document.write( "Yes" ); else document.write( "No" ); </script> |
Output:
Yes
Time Complexity: O(logK n)
Space Complexity: O(1)
Optimized Approach:
This approach avoids the need to convert n to base k and check whether it can be represented using only the digits 0 and 1. It also avoids the need to track whether a 1 has already been seen. This results in a simpler and more efficient algorithm.
Here’s a step-by-step explanation of the code:
- Define the isPrime function which takes an integer n as input and returns true if n is prime, and false otherwise.
- Define the isSumOfPrimes function with parameter n.
- Loop over all numbers from 2 to n/2 (inclusive) as potential prime numbers, and check whether each one is a prime and whether the difference between n and that number is also a prime. The loop continues until the first pair of primes is found.
- If a pair of primes is found, return true. Otherwise, return false.
- In the main function, set n to the desired value.
- Call the isSumOfPrimes function with n.
- If the function returns true, print “Yes” to the console, indicating that n can be expressed as the sum of two prime numbers. Otherwise, print “No”.
C++
#include <iostream> using namespace std; bool isPowerOfK( int n, int k) { // Check for base cases if (n == 0 || k == 0 || k == 1) { return false ; } // Check if n is a power of k while (n % k == 0) { n /= k; } return n == 1; } int main() { int n = 64, k = 4; if (isPowerOfK(n, k)) { cout << "Yes" ; } else { cout << "No" ; } return 0; } |
Java
class GFG { static boolean isPowerOfK( int n, int k) { // Check for base cases if (n == 0 || k == 0 || k == 1 ) { return false ; } // Check if n is a power of k while (n % k == 0 ) { n /= k; } return n == 1 ; } public static void main(String[] args) { int n = 64 , k = 4 ; if (isPowerOfK(n, k)) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } } |
Python3
def isPowerOfK(n, k): # Check for base cases if n = = 0 or k = = 0 or k = = 1 : return False # Check if n is a power of k while n % k = = 0 : n / / = k return n = = 1 n = 64 k = 4 if isPowerOfK(n, k): print ( "Yes" ) else : print ( "No" ) |
C#
using System; class GFG { static bool IsPowerOfK( int n, int k) { // Check for base cases if (n == 0 || k == 0 || k == 1) { return false ; } // Check if n is a power of k while (n % k == 0) { n /= k; } return n == 1; } static void Main( string [] args) { int n = 64, k = 4; if (IsPowerOfK(n, k)) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } |
Javascript
function isPowerOfK(n, k) { // Check for base cases if (n === 0 || k === 0 || k === 1) { return false ; } // Check if n is a power of k while (n % k === 0) { n = Math.floor(n / k); } return n === 1; } let n = 64; let k = 4; if (isPowerOfK(n, k)) { console.log( "Yes" ); } else { console.log( "No" ); } |
OUTPUT:
YES
Time Complexity: O(logK n)
Space Complexity: O(1)
Contact Us