Tutorialspoint.dev

Check if a number is a power of another number

Given two positive numbers x and y, check if y is a power of x or not.

Examples :

Input:  x = 10, y = 1
Output: True
x^0 = 1

Input:  x = 10, y = 1000
Output: True
x^3 = 1

Input:  x = 10, y = 1001
Output: False



A simple solution is to repeatedly compute powers of x. If a power becomes equal to y, then y is a power, else not.

C++

// C++ program to check if a number is power of
// another number
#include <bits/stdc++.h>
using namespace std;
  
/* Returns 1 if y is a power of x */
bool isPower(int x, long int y)
{
    // The only power of 1 is 1 itself
    if (x == 1)
        return (y == 1);
  
    // Repeatedly comput power of x
    long int pow = 1;
    while (pow < y)
        pow *= x;
  
    // Check if power of x becomes y
    return (pow == y);
}
  
/* Driver program to test above function */
int main()
{
    cout << isPower(10, 1) << endl;
    cout << isPower(1, 20) << endl;
    cout << isPower(2, 128) << endl;
    cout << isPower(2, 30) << endl;
    return 0;
}

Java

// Java program to check if a number is power of
// another number
public class Test {
    // driver method to test power method
    public static void main(String[] args)
    {
        // check the result for true/false and print.
        System.out.println(isPower(10, 1) ? 1 : 0);
        System.out.println(isPower(1, 20) ? 1 : 0);
        System.out.println(isPower(2, 128) ? 1 : 0);
        System.out.println(isPower(2, 30) ? 1 : 0);
    }
    /* Returns true if y is a power of x */
    public static boolean isPower(int x, int y)
    {
        // The only power of 1 is 1 itself
        if (x == 1)
            return (y == 1);
  
        // Repeatedly compute power of x
        int pow = 1;
        while (pow < y)
            pow = pow * x;
  
        // Check if power of x becomes y
        return (pow == y);
    }
}
  
// This code is contributed by Jyotsna.

Python3

# python program to check
# if a number is power of
# another number
  
# Returns true if y is a
# power of x 
def isPower (x, y):
      
    # The only power of 1
    # is 1 itself
    if (x == 1):
        return (y == 1)
          
    # Repeatedly compute
    # power of x
    pow = 1
    while (pow < y):
        pow = pow * x
  
    # Check if power of x
    # becomes y
    return (pow == y)
      
      
# Driver Code
# check the result for
# true/false and print.
if(isPower(10, 1)):
    print(1)
else:
    print(0)
  
if(isPower(1, 20)):
    print(1)
else:
    print(0)
if(isPower(2, 128)):
    print(1)
else:
    print(0)
if(isPower(2, 30)):
    print(1)
else:
    print(0)
      
# This code is contributed
# by Sam007.

/div>

C#

// C# program to check if a number 
// is power of another number
using System;
  
class GFG
{
      
    // Returns true if y is a power of x 
    public static bool isPower (int x, int y)
    {
        // The only power of 1 is 1 itself
        if (x == 1)
        return (y == 1);
  
        // Repeatedly compute power of x
        int pow = 1;
        while (pow < y)
        pow = pow * x;
  
        // Check if power of x becomes y
        return (pow == y);
    }
      
    // Driver Code
    public static void Main ()
    {
        //check the result for true/false and print.
        Console.WriteLine(isPower(10, 1) ? 1 : 0);
        Console.WriteLine(isPower(1, 20) ? 1 : 0);
        Console.WriteLine(isPower(2, 128) ? 1 : 0);
        Console.WriteLine(isPower(2, 30) ? 1 : 0);
    }
      
}
  
// This code is contributed by Sam007

PHP

<?php
// PHP program to check if a 
// number is power of another number
  
/* Returns 1 if y is a power of x */
function isPower($x, $y)
{
    // The only power of 1 is 1 itself
    if ($x == 1)
        return ($y == 1 ? 1 : 0);
  
    // Repeatedly comput power of x
    $pow = 1;
    while ($pow < $y)
        $pow *= $x;
  
    // Check if power of x becomes y
    return ($pow == $y ? 1 : 0);
}
  
// Driver Code
echo isPower(10, 1) . " ";
echo isPower(1, 20) . " ";
echo isPower(2, 128) . " ";
echo isPower(2, 30) . " ";
  
// This code is contributed by mits
?>

Output:

1
0
1
0

Time complexity of above solution is O(Logxy)

Optimization:
We can optimize above solution to work in O(Log Log y). The idea is to do squaring of power instead of multiplying it with x, i.e., compare y with x^2, x^4, x^8, …etc. If x becomes equal to y, return true. If x becomes more than y, then we do binary search for power of x between previous power and current power, i.e., between x^i and x^(i/2).

Following are detailed step.

1) Initialize pow = x, i = 1
2) while (pow < y)
   {
      pow = pow*pow 
      i *= 2
   }    
3) If pow == y
     return true;
4) Else construct an array of powers
   from x^i to x^(i/2)
5) Binary Search for y in array constructed
   in step 4. If not found, return false. 
   Else return true.

Alternate Solution :
The idea is to take log of y in base x. If it turns out to be an integer, we return true. Else false.

C++

// CPP program to check given number number y
// is power of x
#include <iostream>
#include <math.h>
using namespace std;
  
bool isPower(int x, int y)
{
    // logarithm function to calculate value
    int res1 = log(y) / log(x);
    double res2 = log(y) / log(x); // Note : this is double
  
    // compare to the result1 or result2 both are equal
    return (res1 == res2);
}
  
// Driven program
int main()
{
    cout << isPower(27, 729) << endl;
    return 0;
}

Java

// Java program to check given 
// number y is power of x
  
class GFG 
{
    static boolean isPower(int x, 
                           int y)
    {
        // logarithm function to
        // calculate value
        int res1 = (int)Math.log(y) / 
                   (int)Math.log(x);
                     
         // Note : this is double          
        double res2 = Math.log(y) / 
                      Math.log(x); 
      
        // compare to the result1 or
        // result2 both are equal
        return (res1 == res2);
    }
      
    // Driver Code
    public static void main(String args[]) 
    {
        if(isPower(27, 729))
            System.out.println("1");
        else
            System.out.println("0");
    }
}
  
// This code is contributed by Sam007

Python3

# Python3 program to check
# given number number y
import math
def isPower(x, y):
    # logarithm function to
    # calculate value
    res1 = math.log(y) / math.log(x);
      
    # Note : this is double
    res2 = math.log(y) / math.log(x); 
  
    # compare to the result1 or
    # result2 both are equal
    return 1 if(res1 == res2) else 0;
  
# Driver Code
if __name__=='__main__':
    print(isPower(27, 729));
  
# This code is contributed by mits

C#

// C# program to check given 
// number y is power of x
using System;
class GFG 
{
static bool isPower(int x, int y)
{
    // logarithm function to
    // calculate value
    int res1 = (int)Math.Log(y) / 
               (int)Math.Log(x);
                  
    // Note : this is double         
    double res2 = Math.Log(y) / 
                  Math.Log(x); 
  
    // compare to the result1 or
    // result2 both are equal
    return (res1 == res2);
}
  
// Driver Code
static void Main() 
{
    if(isPower(27, 729))
        Console.WriteLine("1");
    else
        Console.WriteLine("0");
}
}
  
// This code is contributed by mits

PHP

<?php
// PHP program to check
// given number number y
function isPower($x, $y)
{
    // logarithm function to
    // calculate value
    $res1 = log($y) / log($x);
      
    // Note : this is double
    $res2 = log($y) / log($x); 
  
    // compare to the result1 or
    // result2 both are equal
    return ($res1 == $res2);
}
  
// Driver Code
echo isPower(27, 729) ;
  
// This code is contributed by Sam007
?>


Output :

1

Thanks to Gyayak Jain for suggesting this solution.



This article is attributed to GeeksforGeeks.org

You Might Also Like

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter