☕ DSA Java Articles

Topics › Bit Manipulation › Advanced Maths

Pow(x,n)

Easy TUF ID 877 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Implement pow(x, n): given a real number x and a 32-bit signed integer n, compute x raised to the power n. The exponent may be negative, in which case the answer is 1 / x^|n|. You may not call the library Math.pow; the point of the exercise is the algorithm, binary exponentiation, which is one of the most reused ideas in competitive programming (modular powers, matrix powers, fast Fibonacci).

Constraints: -100.0 < x < 100.0, -2^31 ≤ n ≤ 2^31 - 1, and either x != 0 or n > 0. Answers are compared with a tolerance of 10^-5; the tests in the Java file use a stricter relative tolerance of 10^-9.

Example 1

x = 2.0, n = 10
answer = 1024.0

Example 2

x = 2.0, n = -2
answer = 0.25          // 1 / 2^2

Example 3

x = 2.1, n = 3
answer = 9.261         // 2.1 * 2.1 * 2.1

Approach 1: Brute force

Intuition. Multiply x by itself |n| times, and if n is negative, take the reciprocal at the end. This is the definition of a power and is exactly right for small exponents. For n near 2^31 it performs two billion multiplications, which is both too slow and, as repeated rounding accumulates, less accurate than necessary.

Algorithm.

  1. Let times = |n|, computed in long.
  2. Start with result = 1.0 and multiply by x times times.
  3. Return 1 / result if n < 0, else result.
static double bruteForce(double x, int n) {
    long times = Math.abs((long) n);          // long: Math.abs(Integer.MIN_VALUE) stays negative in int
    double result = 1.0;
    for (long i = 0; i < times; i++) result *= x;
    return n < 0 ? 1.0 / result : result;
}

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

Note the cast before Math.abs. Math.abs(Integer.MIN_VALUE) is Integer.MIN_VALUE (there is no positive counterpart in 32 bits), so an int version would loop zero times and return 1.0 for every x.

Approach 2: Better, recursive binary exponentiation

Intuition. Halve the problem instead of decrementing it. x^n = (x^(n/2))^2 when n is even, and x^n = (x^(n/2))^2 × x when n is odd (with integer division, so n/2 rounds down and the odd case supplies the missing factor). Each recursive call halves the exponent, so there are only about log2(n) levels. The one trap is to compute x^(n/2) once and square it; calling the function twice (pow(x, n/2) * pow(x, n/2)) doubles the work at every level and the running time collapses back to O(n).

Negative exponents are handled up front by replacing x with 1 / x and n with -n, done in long because -Integer.MIN_VALUE does not fit in an int.

Algorithm.

  1. Convert n to a long exponent. If it is negative, set x = 1 / x and negate the exponent.
  2. powRecursive(x, 0) = 1.
  3. Otherwise compute half = powRecursive(x, n / 2) and return half × half, times x if n is odd.
static double better(double x, int n) {
    long exponent = n;                        // long so that -Integer.MIN_VALUE is representable
    if (exponent < 0) {
        x = 1.0 / x;
        exponent = -exponent;
    }
    return powRecursive(x, exponent);
}

private static double powRecursive(double x, long n) {
    if (n == 0) return 1.0;
    double half = powRecursive(x, n / 2);
    return (n % 2 == 0) ? half * half : half * half * x;
}

Complexity. Time O(log n): the exponent halves on every call. Space O(log n) for the recursion stack, at most 32 frames here.

Approach 3: Optimal, iterative binary exponentiation

Intuition. Read the exponent in binary. For n = 10 = 1010₂, x^10 = x^8 × x^2: the set bits of n say which powers x^(2^k) to multiply together. Maintain a running base that is squared at every step (x, x^2, x^4, x^8, ...) and shift the exponent right one bit at a time; whenever the current lowest bit is 1, multiply the base into the result. This is the recursion unrolled into a loop: same O(log n) multiplications, no stack, and it is the form that generalises directly to modular arithmetic and matrix powers.

Algorithm.

  1. Convert n to long; if negative, replace x with 1 / x and negate the exponent.
  2. result = 1.0.
  3. While exponent > 0: if exponent & 1 is 1, result *= x; then x *= x and exponent >>= 1.
  4. Return result.
static double optimal(double x, int n) {
    long exponent = n;
    if (exponent < 0) {
        x = 1.0 / x;
        exponent = -exponent;
    }
    double result = 1.0;
    while (exponent > 0) {
        if ((exponent & 1) == 1) result *= x;   // this bit of n is set, so x^(2^k) belongs in the answer
        x *= x;                                 // x^(2^k) -> x^(2^(k+1))
        exponent >>= 1;
    }
    return result;
}

Dry run on x = 2.0, n = 10 (1010₂):

exponent (binary) lowest bit result x (after squaring)
1010 0 1 4
101 1 1 × 4 = 4 16
10 0 4 256
1 1 4 × 256 = 1024 65536
0 loop ends 1024  

The bases consumed were x^2 = 4 and x^8 = 256, exactly the set bits of 10. Four iterations instead of ten multiplications; for n = 2^31 - 1 it is 31 iterations instead of two billion.

Complexity. Time O(log n): one iteration per bit of n. Space O(1).

Why invert x first rather than the result at the end? Both are mathematically identical and both are fine in floating point for this problem. Inverting first keeps the loop oblivious to the sign, which matters when the same loop is reused for modular exponentiation (where “inverse” means a modular inverse and must be applied to the base).

Edge cases and pitfalls