Check if a number can be expressed as power | Set 2 (Using Log)
Check if a number can be expressed as x^y (x raised to power y)
Given a positive integer n, find if it can be expressed as x^y where y > 1 and x > 0. x and y both are integers.
Examples :
Input: n = 8 Output: true 8 can be expressed as 2^3 Input: n = 49 Output: true 49 can be expressed as 7^2 Input: n = 48 Output: false 48 can't be expressed as x^y
We have discussed two different approaches in below post.
Check if a number can be expressed as x^y (x raised to power y).
The idea is find Log n in different bases from 2 to square root of n. If Log n for a base becomes integer then result is true, else result is false.
C++
// CPP program to find if a number // can be expressed as x raised to // power y. #include <bits/stdc++.h> using namespace std; bool isPower(unsigned int n) { // Find Log n in different bases // and check if the value is an // integer for ( int x=2; x<= sqrt (n); x++) { float f = log (n) / log (x); if ((f - ( int )f) == 0.0) return true ; } return false ; } // Driver code int main() { for ( int i = 2; i < 100; i++) if (isPower(i)) cout << i << " " ; return 0; } |
Java
// Java program to find if a number // can be expressed as x raised to // power y. class GFG { static boolean isPower( int n) { // Find Log n in different // bases and check if the // value is an integer for ( int x = 2 ; x <= ( int )Math.sqrt(n); x++) { float f = ( float )Math.log(n) / ( float ) Math.log(x); if ((f - ( int )f) == 0.0 ) return true ; } return false ; } // Driver code public static void main(String args[]) { for ( int i = 2 ; i < 100 ; i++) if (isPower(i)) System.out.print( i + " " ); } } // This code is contributed by Sam007 |
Python3
# Python3 program to find if a number # can be expressed as x raised to # power y. import math def isPower(n): # Find Log n in different # bases and check if the # value is an integer for x in range ( 2 , int (math.sqrt(n)) + 1 ): f = math.log(n) / math.log(x); if ((f - int (f)) = = 0.0 ): return True ; return False ; # Driver code for i in range ( 2 , 100 ): if (isPower(i)): print (i, end = " " ); # This code is contributed by mits |
C#
// C# program to find if a number // can be expressed as x raised to // power y. using System; class GFG { static bool isPower( int n) { // Find Log n in different // bases and check if the // value is an integer for ( int x = 2; x <= ( int )Math.Sqrt(n); x++) { float f = ( float )Math.Log(n) / ( float ) Math.Log(x); if ((f - ( int )f) == 0.0) return true ; } return false ; } // Driver Code public static void Main() { for ( int i = 2; i < 100; i++) if (isPower(i)) Console.Write( i + " " ); } } // This code is contributed by Sam007 |
PHP
<?php // PHP program to find if a number // can be expressed as x raised to // power y. function isPower( $n ) { // Find Log n in different // bases and check if the // value is an integer for ( $x = 2; $x <= sqrt( $n ); $x ++) { $f = log( $n ) / log( $x ); if (( $f - (int) $f ) == 0.0) return true; } return false; } // Driver code for ( $i = 2; $i < 100; $i ++) if (isPower((int) $i )) echo $i . " " ; // This code is contributed by Sam007 ?> |
Javascript
<script> // javascript program to find if a number // can be expressed as x raised to // power y. function isPower(n) { // Find Log n in different // bases and check if the // value is an integer for (x = 2; x <= parseInt( Math.sqrt(n)); x++) { var f = Math.log(n) / Math.log(x); if ((f - parseInt( f)) == 0.0) return true ; } return false ; } // Driver code for (i = 2; i < 100; i++) if (isPower(i)) document.write(i + " " ); // This code contributed by Rajput-Ji </script> |
Output:
4 8 9 16 25 27 32 36 49 64 81
Time Complexity : O(sqrt(N))
Auxiliary Space : O(1) ,as we are not using any extra space