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)₂. Since first digit is 1 and remaining are zero. Hence 16 can be expressed as power of 2. Count the length of (10000)₂ 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)₃. Since there are two non-zero digit, hence 20 cannot be expressed as power of 3.
 

// 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 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. 

# 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# 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 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 ?> 

<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(log_K 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:

1. Define the isPrime function which takes an integer n as input and returns true if n is prime, and false otherwise.
2. Define the isSumOfPrimes function with parameter n.
3. 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.
4. If a pair of primes is found, return true. Otherwise, return false.
5. In the main function, set n to the desired value.
6. Call the isSumOfPrimes function with n.
7. 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".

#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; } 

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");  }  } } 

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") 

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");  }  } } 

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(log_K n)

Space Complexity: O(1)