NUHMAN.com

Introduction

LeetCode 50: Pow(x, n) challenges you to efficiently compute x raised to the power of n (i.e., xⁿ). While a naive solution might multiply x repeatedly, the optimal approach uses Fast Exponentiation, also known as Exponentiation by Squaring, which runs in logarithmic time.

This is a classic math problem often used in interviews to test your ability to implement optimized recursive or iterative algorithms.

Problem Statement

Implement the function:

go

func myPow(x float64, n int) float64

Calculate x raised to the power n (i.e., xⁿ). The function must handle both positive and negative exponents, and run efficiently for large n.

Examples

Example 1:

go

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

Example 2:

go

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

Example 3:

go

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

Approach: Fast Exponentiation (Binary Power)

To efficiently compute xⁿ, we use:

• Divide and Conquer strategy.
• For even n: xⁿ = (x²)^(n/2)
• For odd n: xⁿ = x * (x²)^((n−1)/2)
• For negative n: x⁻ⁿ = 1 / xⁿ

This reduces the number of multiplications to O(log n).

Go Implementation

✅ Recursive Solution (Elegant and efficient):

go

func myPow(x float64, n int) float64 {
    // Convert to int64 to handle edge cases like n = math.MinInt32
    N := int64(n)
    if N < 0 {
        x = 1 / x
        N = -N
    }
    return fastPow(x, N)
}

func fastPow(x float64, n int64) float64 {
    if n == 0 {
        return 1.0
    }
    half := fastPow(x, n / 2)
    if n%2 == 0 {
        return half * half
    } else {
        return half * half * x
    }
}

Example Walkthrough

Input: x = 2.0, n = 10

Recursive stack will look like:

• fastPow(2.0, 10)
• fastPow(2.0, 5)
• fastPow(2.0, 2)
• fastPow(2.0, 1)
• fastPow(2.0, 0) → returns 1

Then as the recursion unwinds:

• fastPow(2.0, 1) → 1 * 1 * 2 = 2
• fastPow(2.0, 2) → 2 * 2 = 4
• fastPow(2.0, 5) → 4 * 4 * 2 = 32
• fastPow(2.0, 10) → 32 * 32 = 1024

Time and Space Complexity

MetricComplexityTime ComplexityO(log n)Space ComplexityO(log n)

• Time: Each call halves the exponent.
• Space: Call stack for recursion is O(log n), or can be O(1) with an iterative version.

Edge Cases to Consider

• x = 0.0, n > 0: Should return 0.0
• n = 0: Always return 1.0 regardless of x
• x = 0, n = 0: Return 1.0 (by mathematical convention)
• Very large or very negative n (e.g. -2^31): Must handle safely using int64

Alternative: Iterative Version (for O(1) space)

go

func myPow(x float64, n int) float64 {
    N := int64(n)
    if N < 0 {
        x = 1 / x
        N = -N
    }
    result := 1.0
    for N > 0 {
        if N%2 == 1 {
            result *= x
        }
        x *= x
        N /= 2
    }
    return result
}

Key Takeaways

• Use fast exponentiation for logarithmic performance.
• Handle negative powers carefully, especially when n == math.MinInt32.
• Know both recursive and iterative forms of this approach.
• Avoid brute-force multiplication for large exponents — it will timeout.