Pow(x, n)

Problem Statement

Implement pow(x, n), which calculates x raised to the power n (i.e., xⁿ).

Examples

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2^(-2) = 1/2^2 = 1/4 = 0.25

Constraints

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31 - 1
• n is an integer
• Either x is not zero or n > 0
• -10^4 <= x^n <= 10^4

Solution Approaches

Approach 1: Brute Force (❌ Too Slow)

Multiply x by itself n times.

public double myPow(double x, int n) {
    if (n == 0) return 1;

    double result = 1;
    long N = Math.abs((long) n);

    for (long i = 0; i < N; i++) {
        result *= x;
    }

    return n < 0 ? 1 / result : result;
}

Time Complexity: O(n) - Too slow for large n Space Complexity: O(1)

This approach will Time Limit Exceeded for large values of n.

Approach 2: Binary Exponentiation (Fast Power) ⭐

Key Insight: Use the property that xⁿ = (x^n/2)²

This reduces the problem size by half at each step!

Recursive Formula:

• If n = 0: return 1
• If n is even: xⁿ = (x^n/2)²
• If n is odd: xⁿ = x × (x^n-1)¹ = x × x^n-1
• If n < 0: xⁿ = 1 / x^-n

Example: Calculate 2¹⁰

2^10 = (2^5)^2
2^5 = 2 × (2^4) = 2 × (2^2)^2
2^4 = (2^2)^2
2^2 = (2^1)^2
2^1 = 2

Working backwards:
2^2 = 4
2^4 = 16
2^5 = 2 × 16 = 32
2^10 = 32 × 32 = 1024

Only 5 multiplications instead of 10!

Binary Representation Method

We can also think of this using binary representation of n.

For n = 10 = 1010₂ (binary):

10 = 8 + 2 = 2^3 + 2^1

x^10 = x^(8+2) = x^8 × x^2

Algorithm:

1. Convert n to binary
2. For each bit (from right to left):
   • If bit is 1: multiply result by current power
   • Square the current power for next bit
3. Handle negative n by taking reciprocal

Example: 3⁵ where 5 = 101₂

Binary of 5: 1 0 1
Position:    2 1 0

result = 1, base = 3

Bit 0 (1): result = result × base = 1 × 3 = 3
           base = base² = 9

Bit 1 (0): Skip multiplication
           base = base² = 81

Bit 2 (1): result = result × base = 3 × 81 = 243

Answer: 243

Time & Space Complexity

Binary Exponentiation:

• Time Complexity: O(log n)

  • We halve n at each step
  • Number of steps = log₂(n)

• Space Complexity:

  • Iterative: O(1)
  • Recursive: O(log n) for call stack

Java Solution (Iterative)

class Solution {
    public double myPow(double x, int n) {
        // Handle edge cases
        if (n == 0) return 1.0;
        if (x == 0) return 0.0;
        if (x == 1) return 1.0;
        if (x == -1) return n % 2 == 0 ? 1.0 : -1.0;

        // Convert to long to handle Integer.MIN_VALUE
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        double result = 1.0;
        double currentProduct = x;

        // Binary exponentiation
        while (N > 0) {
            // If current bit is 1, multiply result
            if ((N & 1) == 1) {
                result *= currentProduct;
            }

            // Square the base for next bit
            currentProduct *= currentProduct;

            // Move to next bit
            N >>= 1;
        }

        return result;
    }
}

Java Solution (Recursive)

class Solution {
    public double myPow(double x, int n) {
        long N = n;

        if (N < 0) {
            x = 1 / x;
            N = -N;
        }

        return fastPow(x, N);
    }

    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;
        } else {
            return half * half * x;
        }
    }
}

Python Solution (Iterative)

def myPow(x: float, n: int) -> float:
    # Handle edge cases
    if n == 0:
        return 1.0
    if x == 0:
        return 0.0
    if x == 1:
        return 1.0
    if x == -1:
        return 1.0 if n % 2 == 0 else -1.0

    # Handle negative power
    N = abs(n)
    if n < 0:
        x = 1 / x

    result = 1.0
    current_product = x

    # Binary exponentiation
    while N > 0:
        # If current bit is 1
        if N & 1:
            result *= current_product

        # Square the base
        current_product *= current_product

        # Right shift
        N >>= 1

    return result

Python Solution (Recursive)

def myPow(x: float, n: int) -> float:
    def fast_pow(base: float, exp: int) -> float:
        if exp == 0:
            return 1.0

        half = fast_pow(base, exp // 2)

        if exp % 2 == 0:
            return half * half
        else:
            return half * half * base

    N = abs(n)
    result = fast_pow(x, N)

    return result if n >= 0 else 1 / result

Edge Cases

Negative Exponent

Input: x = 2, n = -2
Output: 0.25
Explanation: 2^(-2) = 1/4 = 0.25

Zero Exponent

Input: x = 2, n = 0
Output: 1
Explanation: Any number to power 0 is 1

Integer Overflow

Input: x = 2, n = Integer.MIN_VALUE (-2147483648)

Must convert to long because -Integer.MIN_VALUE overflows!

Negative Base

Input: x = -2, n = 3
Output: -8

Input: x = -2, n = 4
Output: 16

Related Problems

• Sqrt(x) (LeetCode 69): Binary search for square root
• Super Pow (LeetCode 372): Modular exponentiation
• Divide Two Integers (LeetCode 29): Division using bit manipulation
• Count Good Numbers (LeetCode 1922): Modular exponentiation

Pattern Recognition

This problem demonstrates:

• Divide and Conquer pattern
• Binary representation optimization
• Bit manipulation (checking bits, right shift)
• Recursive vs Iterative tradeoffs

Common Mistakes

1. ❌ Using O(n) brute force approach - TLE for large n
2. ❌ Not handling Integer.MIN_VALUE (using int instead of long)
3. ❌ Incorrect handling of negative exponents
4. ❌ Not optimizing - missing the log(n) solution
5. ❌ Off-by-one errors in recursive base case
6. ❌ Precision issues with floating point (though usually acceptable)

Tips for Interviews

• Start with brute force but immediately mention it's O(n) and too slow
• Explain binary exponentiation - this is the key insight
• Draw the recursion tree for small example like 2¹⁰
• Mention both approaches: recursive and iterative
• Handle edge cases: negative n, Integer.MIN_VALUE, x = 0, n = 0
• Discuss complexity: O(log n) time is huge improvement over O(n)
• Binary representation: Optionally explain the bit manipulation view
• Overflow: Explain why we use long instead of int

Visual Understanding

Recursion Tree for 2¹⁰

                    2^10
                  /      \
              2^5          2^5
            /    \
         2^2      2^2
        /   \
      2^1   2^1
     /
    2^0

Each level halves the exponent → O(log n) depth

Iterative Binary Approach for 2¹⁰

n = 10 = 1010₂

Step 1: Check bit 0 (0): skip, square base: 2² = 4
Step 2: Check bit 1 (1): multiply result (1 × 4 = 4), square base: 4² = 16
Step 3: Check bit 2 (0): skip, square base: 16² = 256
Step 4: Check bit 3 (1): multiply result (4 × 256 = 1024)

Result: 1024

Follow-Up Questions

1. Q: Can you do better than O(log n)?

   • A: No, we must process each bit of n

2. Q: What about very large exponents (modular exponentiation)?

   • A: Use (a × b) % m = ((a % m) × (b % m)) % m property

3. Q: How to handle matrix exponentiation?

   • A: Same algorithm, but multiply matrices instead of numbers

4. Q: What if n is a floating point number?

   • A: Different problem - need Taylor series or other numerical methods

Why Binary Exponentiation?

Comparison:

• Naive: 2¹⁰⁰⁰ requires 1000 multiplications
• Binary: 2¹⁰⁰⁰ requires only ~10 multiplications (log₂ 1000 ≈ 10)

This is a 1000× speedup!

Complexity Comparison

| Approach | Time | Space | Notes | |----------|------|-------|-------| | Brute Force | O(n) | O(1) | TLE for large n | | Binary (Iterative) | O(log n) | O(1) | Optimal ⭐ | | Binary (Recursive) | O(log n) | O(log n) | Call stack space |

Recommendation: Use iterative binary exponentiation for best space complexity.