Check if a number can be expressed as x raised to power y | Set 2

Given a positive integer N, return true if there exist 2 integers x and y with following conditions:
1. N = x^y
2. x > 0
3. y > 1
If no such x and y can be found for the given integer N, then return false.
Please check out another solution to the problem here:
Check if a number can be expressed as x raised to power y | Set 1

Example:
Consider the number: 125
Since 125 can be written as x^y where x = 5, y = 3, so return true.
Consider the number: 120
As no two integers exist for which we can write 120 = x^y, return false.
Please check out the video below for detailed explanation of the algorithm with animations.


Question Asked in

Google, Amazon


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Algorithm/Insights

Instead of repeated divisions as given in previous method, we can apply mathematical formula as described:
Given a number a, we have to find integers x and y, such that:
     a = x^y
If we take log on both sides, we get:
     log a = log (x^y)
     log a = y log x
     y = log a / log x
Hence, we have to find an integer x for which RHS gives an integer y.

Algorithm:
1: Starting with i = 2, if (log a / log i) is an integer then return true.
2: Else increment i by 1 till i < √a.
3: If no such i is found, return false.

Why √number?
We want to find integers x and y (>1) such that x^y = given number 'a'.
i.e. if for any x, if x^2 = a or x^3 = a or ... x^y = a, for some integer y, return true.
Can we have upper limit on value of x from above condition?
Let's find out!
Now, we know that √a * √a = a
Then for any number, x > √a, x^2 will always be greater than a.
                x* x > √a * √a  = a
As x^2  > a, x^3  > a, x^4 > a ... i.e. any other power of x will also be greater than a.
So the upper limit on value of x is √a.

Lets take one example to understand the algorithm.
Number = 100, iterate for i = 2 to √100 = 10
log 100 / log 2   = 6.643856189774725
log 100 / log 3   = 4.19180654857877
log 100 / log 4   = 3.3219280948873626
log 100 / log 5   = 2.8613531161467867
log 100 / log 6   = 2.570194417876938
log 100 / log 7   = 2.366589324909877
log 100 / log 8   = 2.2146187299249087
log 100 / log 9   = 2.095903274289385
log 100 / log 10 = 2.0
As 2 is an integer, return true.

Lets take another example.
Number = 625, iterate for i = 2 to √625 = 25
log 625 / log 2 = 9.287712379549449
log 625 / log 3 = 5.859894082871707
log 625 / log 4 = 4.643856189774724
log 625 / log 5 = 4.0
As 4 is an integer, return true.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.saurabh;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a positive integer, find if it can be expressed by integers x and y as
 * x^y where y > 1 and x > 0.
 * 
 * Example
 * Input : 625
 * Output : true as 5^4 = 625
 * 
 * @author Saurabh
 */
public class Power {

    public static boolean check(int a) {
        if (a == 1)
            return true;
        for (int i = 2; i <= Math.sqrt(a); i++) {
            double value = Math.log(a) / Math.log(i);
            if ((value - (int) value) < 0.000000001) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(check(625));
    }
}
		

Contribution

  • Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.


    Saurabh Kumar