Pow(x, n) - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "Pow(x, n)" Problem in Go

Difficulty: Medium | Tags: Math, Recursion

Introduction

Calculating the power of a number is a fundamental mathematical operation with applications in various domains. The problem requires implementing an efficient algorithm to compute x raised to the power n, handling both positive and negative exponents.

Problem Analysis

The problem involves computing x^n efficiently, especially for large values of n. A brute-force approach would multiply x by itself n times, but this is inefficient for large n. Instead, we can use a recursive approach with divide-and-conquer to reduce the time complexity to O(log n).

Solution Approach

The solution leverages the mathematical property that x^n can be broken down into (x^(n/2))^2 if n is even, or x * (x^(n/2))^2 if n is odd. This reduces the problem size by half at each step, leading to logarithmic time complexity. Negative exponents are handled by computing the reciprocal of the positive power.

Go Implementation


func myPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    if n < 0 {
        x = 1 / x
        n = -n
    }
    return fastPow(x, n)
}
func fastPow(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    half := fastPow(x, n/2)
    if n%2 == 0 {
        return half * half
    } else {
        return half * half * x
    }
}

Complexity Analysis

The time complexity is O(log n) due to the recursive halving of the problem size. The space complexity is O(log n) as well, due to the recursion stack depth.

Testing and Examples

Test cases include:
1. x = 2.0, n = 10 → 1024.0
2. x = 2.1, n = 3 → 9.261
3. x = 2.0, n = -2 → 0.25
Edge cases: n = 0 (returns 1), x = 0 and n = 1 (returns 0).

Best Practices and Tips

Key takeaways include using recursion for logarithmic time complexity, handling negative exponents by reciprocating the base, and ensuring edge cases like n = 0 are covered. Optimizations like memoization can further improve performance for repeated calculations.

Read more