Check if a Number is a Power of Another Number in Java

In this problem, we are asked to determine if a number y is a power of another number x. Formally, we want to know if there exists an integer n ≥ 0 such that: xn=y

This problem often comes up in coding interviews and requires careful handling of edge cases.

Problem Examples

Example 1

Input: x = 2, y = 8
Output: true

Explanation: (2^3 = 8), so 8 is a power of 2.

Example 2

Input: x = 1, y = 8
Output: false

Explanation: (1^n = 1) for all integers n ≥ 0. 8 is not equal to 1.

Example 3

Input: x = 46, y = 205962976
Output: true

Explanation: (46^5 = 205962976), so 205962976 is a power of 46.

Key Observations

If y == 1, the answer is always true because (x^0 = 1) for any positive integer x.
If x == 1, then (1^n = 1) only. So y must be exactly 1.
For general cases, we can keep multiplying x until the result is greater than or equal to y.
If we reach y exactly while multiplying, y is a power of x. Otherwise, it is not.

Java Implementation

class Solution {
    public boolean isPower(int x, int y) {
        // Step 1: Handle edge cases
        if (y == 1) return true;       // x^0 = 1
        if (x == 1) return y == 1;     // Only 1^n = 1

        long curr = 1;  // Use long to avoid integer overflow

        // Step 2: Multiply x repeatedly until curr >= y
        while (curr < y) {
            curr *= x;
        }

        // Step 3: Check if we exactly reached y
        return curr == y;
    }
}

How the Code Works

Step 1: Edge Cases

if (y == 1) return true;
if (x == 1) return y == 1;

If y = 1, any x^0 = 1 is valid → return true.
If x = 1, the only valid power is 1. So y must be 1.

Step 2: Iterative Multiplication

long curr = 1;
while (curr < y) {
    curr *= x;
}

Start from 1 and multiply by x repeatedly.
Stop when the current value is greater than or equal to y.
Use long to prevent integer overflow for large values.

Step 3: Check Result

return curr == y;

If we exactly reached y, then y is a power of x.
Otherwise, it is not.

Examples with Output

x	y	Output	Explanation
2	8	true	(2^3 = 8)
1	8	false	(1^n) never equals 8
46	205962976	true	(46^5 = 205962976)
50	312500000	true	(50^5 = 312500000)
5	1	true	(5^0 = 1)

Complexity Analysis

Time Complexity: (O(\log_x y))
- Each multiplication increases the exponent by 1, so we loop approximately (\log_x y) times.
Space Complexity: (O(1))
- Only a few variables are used; no extra space is required.

Conclusion

This solution efficiently checks if a number y is a power of x, handles edge cases properly, and avoids overflow issues by using long.