11.3 Pow(x, n)

11.3.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 50
• Difficulty: Medium
• URL: https://leetcode.com/problems/powx-n/
• Tags: NeetCode 150
• Techniques: Divide and Conquer, Recursion, Math

11.3.2 Description

Implement pow(x, n) which computes x raised to the power n (x^n) for integer n.

11.3.3 Examples

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

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

11.3.4 Constraints

• -100 <= x <= 100
• -2^31 <= n <= 2^31 - 1

11.3.5 Solution - Fast Exponentiation

11.3.5.1 Walkthrough

Use exponentiation by squaring: x^n = (x^{n/2})^2 * x^{n%2}. Handle negative exponents by inverting x and negating n. Base cases are n == 0 -> 1, n == 1 -> x.

11.3.5.2 Analysis

• Time Complexity: O(log |n|)
• Space Complexity: O(log |n|) recursion stack

11.3.5.3 Implementation Steps

1. If n == 0, return 1.
2. If n < 0, invert x and negate n.
3. Recursively compute half = pow(x, n / 2).
4. Combine as half * half * (n % 2 == 0 ? 1 : x).

11.3.5.4 Code - Java

public double myPow(double x, int n) {
    long exp = n;
    if (exp < 0) {
        x = 1 / x;
        exp = -exp;
    }
    return fastPow(x, exp);
}

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