Tutorialspoint.dev

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

Output:

Yes

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter