Pow(x, n)
Problem Statement
Pow(x, n)
is a mathematical function to calculate the value of x
raised to the power of n
(i.e., x^n
).
Given a floating-point value x
and an integer value n
, implement the myPow(x, n)
function, which calculates x
raised to the power n
.
You may not use any built-in library functions.
Example 1:
Input: x = 2.00000, n = 5Output: 32.00000
Example 2:
Input: x = 1.10000, n = 10Output: 2.59374
Example 3:
Input: x = 2.00000, n = -3Output: 0.12500
Constraints:
-100.0 < x < 100.0
-1000 <= n <= 1000
n
is an integer.- If
x = 0
, thenn
will be positive.
Recommended Time and Space Complexity
Aim for a solution with O(log n)
time complexity.
Hint 1
Consider using a divide-and-conquer approach.
Hint 2
Think about how to handle negative exponents.
Hint 3
Binary exponentiation can significantly improve efficiency.
Solution
Brute Force
def my_pow_brute_force(x: float, n: int) -> float: if x == 0: return 0 if n == 0: return 1
res = 1 for _ in range(abs(n)): res *= x return res if n >= 0 else 1 / res
Time complexity: O(n)
Space complexity: O(1)
Binary Exponentiation (Recursive)
def my_pow_recursive(x: float, n: int) -> float: def helper(x, n): if x == 0: return 0 if n == 0: return 1
res = helper(x * x, n // 2) return x * res if n % 2 else res
res = helper(x, abs(n)) return res if n >= 0 else 1 / res
Time complexity: O(log n)
Space complexity: O(log n)
Binary Exponentiation (Iterative)
def my_pow_iterative(x: float, n: int) -> float: if x == 0: return 0 if n == 0: return 1
res = 1 power = abs(n)
while power: if power & 1: res *= x x *= x power >>= 1
return res if n >= 0 else 1 / res
Time complexity: O(log n)
Space complexity: O(1)