Command Palette

Search for a command to run...

Hectal
Problem 12.2 · RecursionMedium

Pow(x, n)

PatternRecursionDivide and Conquer

What it teaches: Fast exponentiation: xⁿ = (x^(n/2))², so the recursion depth is log n, not n.

Practise it on judges as “Pow(x, n)”.

The problem

Implement myPow(x, n), computing x raised to the power n (n may be negative).

Example 1

Input: x = 2.0, n = 10
Output: 1024.0

Example 2

Input: x = 2.1, n = 3
Output: 9.261

Example 3

Input: x = 2.0, n = -2
Output: 0.25

Constraints

  • −100 < x < 100
  • −2³¹ ≤ n ≤ 2³¹ − 1

Pattern clues in the wording

  • → Repeated multiplication with a huge exponent
  • → Halve the problem each step

These clues point to Recursion: Solve the problem by solving a smaller version of it, with a base case that stops the calls.

Stuck? Take one hint at a time

Solution.java · starter
class Solution {
    public double myPow(double x, int n) {
        return 1.0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
x = 2
n = 10
1024
2
x = 2.1
n = 3
9.261
3
x = 2
n = -2
0.25

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Optimal: halve the exponent · O(log n)
1

Optimal: halve the exponent

Time O(log n) Space O(log n) stack

Compute half = pow(x, n / 2) once, square it, and multiply by x if n is odd. Use a long for n so −Integer.MIN_VALUE doesn't overflow.

Approach 1
class Solution {
    public double myPow(double x, int n) {
        long N = n;                          // -Integer.MIN_VALUE overflows an int
        if (N < 0) { x = 1 / x; N = -N; }
        return pow(x, N);
    }

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

Verdict: About 31 levels for any int exponent.

Before you submit

Edge cases and common mistakes

Test these inputs

  • n = 0 → 1
  • n negative
  • n = Integer.MIN_VALUE
  • x = 0 with positive n

Mistakes people make

  • Calling pow(x, n/2) twice per level (back to O(n)).
  • Negating an int n of Integer.MIN_VALUE.

Interview

Follow-up questions

How do you do it iteratively?