Pow(x, n)
Implement `pow(x, n)`, which calculates `x` raised to the power `n` (i.e., `x^n`).
Examples
Constraints
-100.0 < x < 100.0-2^31 <= n <= 2^31 - 1n is an integer.Either x is not zero or n > 0.-10^4 <= x^n <= 10^4
Fast Power (Divide and Conquer)
Approach
Instead of multiplying `x` by itself `n` times (which takes O(n) time and will result in TLE for large `n`), we can use the property of exponents: If `n` is even, `x^n = x^(n/2) * x^(n/2)` = `(x^2)^(n/2)`. If `n` is odd, `x^n = x * (x^2)^((n-1)/2)`. We can calculate this recursively or iteratively in O(log n) time. Note: When `n` is negative, we can compute `x^-n` as `(1/x)^n`. We must be careful with the edge case where `n = -2^31`, as `-n` will overflow a 32-bit signed integer. We can handle this by casting `n` to a 64-bit integer (long) or by multiplying one `1/x` separately before making `n` positive.
Complexity Analysis
Time complexity is O(log n) since we halve `n` at each step. Space complexity is O(log n) for the recursion stack in Python, and O(1) for the iterative Java solution.
class Solution { public double myPow(double x, int n) { // Use long to prevent overflow when n is Integer.MIN_VALUE long N = n; if (N < 0) { x = 1 / x; N = -N; } double ans = 1; double currentProduct = x; for (long i = N; i > 0; i /= 2) { if ((i % 2) == 1) { ans = ans * currentProduct; } currentProduct = currentProduct * currentProduct; } return ans; }}