Check for Power

JavaView on GFG

Time: O(log_x(y))

Space: O(1)

Intuition

Check if a number is a power of 2 (or given base k). Bit trick for power of 2.

Algorithm

1Power of 2: n > 0 && (n & (n-1)) == 0.
2Power of k: repeatedly divide by k; check remainder is 0 and quotient reaches 1.

Common Pitfalls

•Edge case: n=1 is k^0 for any k. n=0 is never a power. For k=1: only n=1.

Check for Power.java

Java


// Approach: Repeatedly multiply x starting from 1 until the product reaches or exceeds y.
// If x == 1, y must also equal 1 (since 1^k == 1 for all k).
// Otherwise keep multiplying: if the product equals y at any point, y is a power of x.
// Using a long prevents integer overflow during multiplication.
// Time: O(log_x(y)) Space: O(1)
class Solution {

    public boolean isPower(int x, int y) {
        long num = 1;
        if (x == 1) {
            return (y == 1);
        }
        while (num < y) {
            num *= x;
        }
        
        return (num == y);
    }
}

Was this solution helpful?