Java  

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

  1. If y == 1, the answer is always true because (x^0 = 1) for any positive integer x.

  2. If x == 1, then (1^n = 1) only. So y must be exactly 1.

  3. For general cases, we can keep multiplying x until the result is greater than or equal to y.

  4. 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

xyOutputExplanation
28true(2^3 = 8)
18false(1^n) never equals 8
46205962976true(46^5 = 205962976)
50312500000true(50^5 = 312500000)
51true(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.

Membership not found