Pow(x, n) · Zachary Short

Problem

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

Approach

1. Base Case: x ∈ S
2. Recursive Case: if x ∈ S, x*n ∈ S
3. JUST KIDDING

My Saving Grace

By some miracle, my Algorithms Professor happended to be covering this exact formula in class just a few days ago. And I remembered it enough to grind through the problem.

Edge Cases

If n is negative, convert it to (1/x)ⁿ
Ex: 2⁻² == (1/2)²

Reflections

I would have absolutely tried to brute force it with a recurrence relation had I not seen the exact formula just a couple days before.

Go Solution

func myPow(x float64, n int) float64 {
    if n <= 1 {
        return baseCase(x,n)
    }

    if isEven(n) {
        return myPow(x*x, n / 2)
    }
    
    return myPow(x*x, n / 2) * x
}

func isEven(n int) bool {
    return n % 2 == 0 
}

func baseCase(x float64, n int) float64 {
    if n < 0 {
        return myPow(1/x, n * -1)
    }

    if n == 0 {
        return 1
    }

    return x
}

Performance

Runtime beats: 100%
Memory beats: 80.48%

Complexity

Time: O(log n)
Space: O(log n)