☕ DSA Java Articles

Topics › Recursion and Backtracking › Get a Strong Hold

Pow(x, n)

Easy TUF ID 2855 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given a real number x and an integer n, compute x^n (x raised to the power n). The exponent may be negative, in which case x^n = 1 / x^(-n).

Constraints: -100.0 < x < 100.0, -2^31 ≤ n ≤ 2^31 - 1, and either x is non-zero or n is positive. The answer fits in a double.

Example 1

x = 2.0, n = 10
answer = 1024.0          // 2 multiplied by itself 10 times

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

The interesting part is the size of n. Two billion multiplications is too slow, so the task is really “compute a power in far fewer than n steps”, and the recursion that does it is one of the most reused ideas in the sheet (modular exponentiation, matrix powers, fast Fibonacci).

Approach 1: Brute force

Intuition. x^n is x multiplied by itself n times, so do exactly that. For a negative exponent compute the positive power and take its reciprocal.

Algorithm.

  1. Let times = |n|, computed in a long.
  2. Multiply result (initially 1.0) by x, times times.
  3. If n < 0 return 1 / result, otherwise result.
static double bruteForce(double x, int n) {
    long times = Math.abs((long) n);             // cast first: Math.abs(Integer.MIN_VALUE) is still negative
    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).

The cast to long before Math.abs is not cosmetic. Integer.MIN_VALUE is -2^31, and +2^31 does not exist as an int, so Math.abs(Integer.MIN_VALUE) returns Integer.MIN_VALUE itself, a negative number, and the loop would run zero times and return 1.0 for every base. Widening first makes the absolute value correct.

With n up to 2^31 - 1 this loop takes seconds, so it is only a reference implementation.

Approach 2: Optimal, recursive fast exponentiation

Intuition. Squaring is the shortcut. x^10 = (x^5)^2, and x^5 = (x^2)^2 · x. Each step halves the exponent, so only about log2(n) multiplications are needed instead of n. The recursion is: x^0 = 1; for n > 0, compute half = x^(n/2) once, then return half · half if n is even and half · half · x if n is odd. A negative exponent is handled up front by replacing x with 1/x and n with -n.

Algorithm.

  1. Widen n to a long e. If e < 0, set x = 1 / x and e = -e.
  2. power(x, e): if e == 0 return 1.
  3. Otherwise half = power(x, e / 2).
  4. Return half * half, times x if e is odd.
static double optimalRecursive(double x, int n) {
    long e = n;                                   // widen before negating: -Integer.MIN_VALUE does not fit in an int
    if (e < 0) {
        x = 1.0 / x;
        e = -e;
    }
    return power(x, e);
}

static double power(double x, long e) {
    if (e == 0) return 1.0;                       // base case: anything to the power 0 is 1
    double half = power(x, e / 2);                // one subproblem of half the size
    return e % 2 == 0 ? half * half : half * half * x;
}

Dry run for x = 2, n = 10:

call e even? half returns
power(2, 0)     1
power(2, 1) odd 1 1 · 1 · 2 = 2
power(2, 2) even 2 2 · 2 = 4
power(2, 5) odd 4 4 · 4 · 2 = 32
power(2, 10) even 32 32 · 32 = 1024

Complexity. Time O(log n): the exponent halves at every level, so there are about 31 levels for the largest int. Space O(log n) for the call stack.

Two details decide whether this is actually logarithmic:

Approach 3: Optimal, iterative binary exponentiation

Intuition. Write the exponent in binary: 10 = 1010₂ = 8 + 2, so x^10 = x^8 · x^2. The powers x^1, x^2, x^4, x^8, ... are each the square of the previous one, so we can generate them in a loop and multiply into the answer exactly those whose bit is set in n. This is the same arithmetic as Approach 2 read from the other end, without recursion.

Algorithm.

  1. Handle a negative exponent as before.
  2. Keep base = x^(2^k) and result = 1.
  3. While e > 0: if the lowest bit of e is 1, result *= base. Then base *= base and shift e right by one bit.
  4. Return result.
static double optimalIterative(double x, int n) {
    long e = n;
    if (e < 0) {
        x = 1.0 / x;
        e = -e;
    }
    double result = 1.0, base = x;                // after k rounds, base = x^(2^k)
    while (e > 0) {
        if ((e & 1) == 1) result *= base;         // this bit is set: x^(2^k) belongs in the product
        base *= base;
        e >>= 1;
    }
    return result;
}

Dry run for x = 2, n = 10:

e (binary) lowest bit result base after squaring
1010 0 1 4
101 1 4 16
10 0 4 256
1 1 4 · 256 = 1024 65536

Complexity. Time O(log n), one iteration per bit of the exponent. Space O(1); this is the version to use when recursion depth or stack usage matters.

Both optimal versions were tested on identical inputs, including n = Integer.MIN_VALUE, where the brute force cannot run in a reasonable time.

Edge cases and pitfalls