Calculate the Power Function

Given a number x and an integer n, compute xⁿ. n may be negative: x⁻ⁿ = 1 / xⁿ.

LeetCode: 50. Pow(x, n)

Example

power(3, 4)  = 81
power(2, -3) = 0.125
power(5, 0)  = 1

Brute force: multiply n times

public class Main {
    static double power(double x, int n) {
        double result = 1.0;
        long count = Math.abs((long) n);
        for (long i = 0; i < count; i++) {
            result *= x;
        }
        return n < 0 ? 1.0 / result : result;
    }

    public static void main(String[] args) {
        System.out.println(power(3, 4) + " " + power(2, -3) + " " + power(5, 0));
    }
}

81.0 0.125 1.0

Time: O(|n|). Space: O(1).

A whole-number double prints with a trailing .0, so 81 appears as 81.0.

Math.abs((long) n) widens n to a long first. Math.abs(n) on an int returns Integer.MIN_VALUE unchanged for n = Integer.MIN_VALUE, because its positive value does not fit in an int, so the loop would see a negative count.

Optimal: exponentiation by squaring

Halve the exponent at every step:

x^n = (x²)^(n/2)        if n is even
x^n = x · (x²)^(n/2)    if n is odd

Iteratively, this reads the bits of n from lowest to highest. base goes through x, x², x⁴, x⁸, ..., and it is multiplied into the result wherever n has a 1 bit. For 3¹³ (13 is 1101 in binary):

public class Main {
    static double power(double x, int n) {
        long exp = Math.abs((long) n);
        double base = x;
        double result = 1.0;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result *= base;
            }
            base *= base;
            exp >>= 1;
        }
        return n < 0 ? 1.0 / result : result;
    }

    public static void main(String[] args) {
        System.out.println(power(3, 4) + " " + power(2, -3) + " " + power(5, 0));
        System.out.println(power(3, 13) + " " + power(1, Integer.MIN_VALUE));
        System.out.println(power(0, 0) + " " + power(0, -1));
    }
}

81.0 0.125 1.0
1594323.0 1.0
1.0 Infinity

Time: O(log |n|). Space: O(1). A recursive version is equally fast but uses O(log |n|) stack.

The standard library provides Math.pow(double, double). For exact integer powers, Math.multiplyExact throws ArithmeticException on int or long overflow.

Edge cases

• n = 0: 1, even for x = 0 (by convention).
• n = Integer.MIN_VALUE: handled by widening to long before Math.abs.
• x = 0 with n < 0: 1.0 / 0.0 is Infinity for double, with no exception.