CODEWITHSUNDEEP
java
Nishant123
Nishant123

Reputation: 1966

How to check whether a number can be represented in the form A^B?

I was recently asked in an interview to write a program to check whether a number can be represented in the form of A^B. I couldn't solve the problem as I weren't even having a correct approach to solve the problem.

Here are a few examples

Input = 4
Output = true

As it can be represented as 2^2

 Input = 536870912
 Output = true

As it can be represented as 2^29

Input = 1024000000
Output = true

As it can be represented as 2^16*5^6 = 32000^2

Can anyone please provide a solution (preferably using Java) to this problem?

Upvotes: 1

Views: 395

Answers (1)

Andreas
Andreas

Reputation: 159114

If you want an answer for X = AB for a known X, with both A ≥ 2 and B ≥ 2 and both being integers, then the shortest search is doing A = B√X for B = 2..n, until A < 2.

public static void findPower(double value) {
    if (value < 1 || value % 1 != 0)
        throw new IllegalArgumentException("Invalid input: " + value);
    boolean found = false;
    for (int exp = 2; ; exp++) {
        long base = Math.round(Math.pow(value, 1.0 / exp));
        if (base < 2)
            break;
        if (Math.pow(base, exp) == value) {
            System.out.printf("%.0f = %d ^ %d%n", value, base, exp);
            found = true;
        }
    }
    if (! found)
        System.out.printf("%.0f has no solution%n", value);
}

TEST

findPower(4);
findPower(123_456);
findPower(536_870_912);
findPower(1_024_000_000);
findPower(2_176_782_336d);
findPower(205_891_132_094_649d);

OUTPUT

4 = 2 ^ 2
123456 has no solution
536870912 = 2 ^ 29
1024000000 = 32000 ^ 2
2176782336 = 46656 ^ 2
2176782336 = 1296 ^ 3
2176782336 = 216 ^ 4
2176782336 = 36 ^ 6
2176782336 = 6 ^ 12
205891132094649 = 14348907 ^ 2
205891132094649 = 59049 ^ 3
205891132094649 = 729 ^ 5
205891132094649 = 243 ^ 6
205891132094649 = 27 ^ 10
205891132094649 = 9 ^ 15
205891132094649 = 3 ^ 30

Upvotes: 2

Related Questions