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

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.

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.

## Algorithm/Insights

Algorithm:
1: Initialize factor = 2.
2: Check if number is divisible by 'factor'. If yes, then keep on dividing the number by factor till it is divisible by factor.
3: After step 2, if we are left with number = 1, then number can be represented as a power of factor, so return true. Else, increment factor by 1.
4: Repeat steps 2 and 3 till factor <= √number.
If no such factor is found, then 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.
Consider the given number as 100.

Number = 100
Initialize factor = 2
On repeated division by 2 we get: 100 -> 50 -> 25
As further division by 2 is not possible and the number(100) is not reduced to 1,
so we increment factor to 3.

factor = 3
As 100 is not divisible by 3 and the number(100) is not reduced to 1,
so increment factor to 4.

factor = 4
On repeated division by 4 we get: 100 -> 25
As further division by 4 is not possible and the number(100) is not reduced to 1,
so increment factor to 5.

factor = 5
On repeated division by 5 we get: 100 -> 20 -> 4
As further division by 5 is not possible and the number(100) is not reduced to 1,
so increment factor to 6.

factor = 6
As 100 is not divisible by 6, increment to 7.

Similarly, as 100 is not divisible by 7, 8 and 9 also,
increment factor to 10.

factor = 10
On repeated division by 10 we get: 100 -> 10 -> 1
As further division by 10 is not possible and the number is reduced to 1, therefore 100 is a power of 10.
Hence, return true.

Please checkout another solution to this problem:
Check if a number can be expressed as x raised to power y | Set 2

## Code Snippet

```
package com.ideserve.questions.saurabh;

/**
* <b>IDeserve <br>
* 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) {
int factor = 2;
while (factor <= Math.sqrt(a)) {
int number = a;
while (number % factor == 0) {
number /= factor;
}
if (number == 1) {
return true;
} else {
factor++;
}
}
return false;
}

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