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 = 1Input: x = 10, y = 1000
Output: True
x^3 = 1Input: x = 10, y = 1001
Output: False
A simple solution is to repeatedly compute the 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 compute 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. |
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) . "\n" ; echo isPower(1, 20) . "\n" ; echo isPower(2, 128) . "\n" ; echo isPower(2, 30) . "\n" ; // This code is contributed by mits ?> |
Javascript
<script> // JavaScript program to check if a number // is power of another number /* Returns true 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); // Repeatedly compute power of x let 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. document.write((isPower(10, 1) ? 1 : 0) + "<br/>" ); document.write((isPower(1, 20) ? 1 : 0) + "<br/>" ); document.write((isPower(2, 128) ? 1 : 0) + "<br/>" ); document.write((isPower(2, 30) ? 1 : 0) + "<br/>" ); </script> |
1 0 1 0
Time complexity: O(Logxy)
Auxiliary space: O(1)
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 y // is power of x #include <iostream> #include <math.h> using namespace std; bool isPower( int x, int y) { // logarithm function to calculate value float res1 = log (y) / log (x); return res1== floor (res1); } // Driven program int main() { cout << isPower(2, 128) << endl; return 0; } //This code is contributed by Anand Agarwal |
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 float res1 = ( float )(Math.log(y) / Math.log(x)); return (res1% 1 == 0 ); } // Driver Code public static void main(String args[]) { if (isPower( 2 , 128 )) System.out.println( "1" ); else System.out.println( "0" ); } } // This code is contributed by Sam007 // This code is Corrected by Anand Agarwal |
Python3
# Python program to check if given number y # is power of x import math def is_power(x, y): # logarithm function to calculate value res1 = math.log(y) / math.log(x) res2 = math.log(y) / math.log(x) # Note: this is float # compare to the result1 or result2 both are equal return res1 = = res2 # Driven program if __name__ = = "__main__" : print (is_power( 2 , 128 )) |
C#
using System; namespace ConsoleApp1 { class Program { // Function to check if a number is power of another number static bool IsPower( int x, int y) { // Use logarithm function to calculate the value double res1 = Math.Log(y) / Math.Log(x); // Note : this is double double res2 = Math.Log(y) / Math.Log(x); // Compare the result1 or result2, they should be equal return (res1 == res2); } static void Main( string [] args) { // Check if 128 is power of 2 if (IsPower(2, 128)) Console.WriteLine( "1" ); else Console.WriteLine( "0" ); } } } // This code is contributed by vinayetbi1. |
PHP
<?php // PHP program to check // given 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(2, 128) ; // This code is contributed by Sam007 ?> |
Javascript
// JavaScript program to check given number y // is power of x function isPower(x, y) { // logarithm function to calculate value const res1 = Math.log(y) / Math.log(x); const res2 = Math.log(y) / Math.log(x); // compare to the result1 or result2 both are equal return (res1 === res2); } // Driven program console.log(isPower(2, 128)); |
1
Time complexity: O(log Y)
Auxiliary space: O(1)
Contact Us