Problem List
Pow(x, n)
May 31, 2025 • Go • math, recursion • medium
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.
Performance
- Runtime beats: 100%
- Memory beats: 80.48%
Complexity
- Time:
O(log n) - Space:
O(log n)
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
}