Implement Pow

JavaView on GFG

Intuition

Fast exponentiation (binary exponentiation): x^n = (x^(n/2))^2, halving n each time.

Algorithm

1If n==0: return 1. If n<0: x=1/x, n=-n.
2If n is even: return pow(x*x, n/2).
3If n is odd: return x * pow(x*x, n/2).

Example Walkthrough

Input: x=2.0, n=10

1.pow(2,10)=pow(4,5)=4*pow(16,2)=4*pow(256,1)=4*256=1024.

Output: 1024.0

Common Pitfalls

•Handle n=INT_MIN carefully (overflow on negation). Use long for n.

Implement Pow.java

Java

// Approach: Fast exponentiation (binary exponentiation). Reduce exponent by half at each step.
// Time: O(log n) Space: O(log n)
class Solution {
    double power(double b, int e) {
        double ans = 1.0;
        int nn = e;
        if (e < 0)
            nn = -1 * e;

        while (nn > 0) {
            if (nn % 2 == 0) {
                b = b * b;
                nn /= 2;
            } else {
                ans = ans * b;
                nn -= 1;
            }
        }

        if (e < 0)
            return (double) 1.0 / (double) ans;

        return ans;
    }
}

Was this solution helpful?