Pow(x, n)
The key idea
Multiplying
x by itself n times is O(n). Instead, square the base and halve the exponent: x^n equals (x*x)^(n/2) when n is even, and x * (x*x)^((n-1)/2) when n is odd. Each step halves the work, so the answer needs only O(log n) multiplications. A negative n is handled by inverting the base to 1/x and using -n.Problem
Implement pow(x, n), which calculates x raised to the power n (that is, x^n). Here x is a floating-point number and n is an integer that may be negative, in which case the result is the reciprocal of the positive power. Return the computed value.
Constraints
-100.0 < x < 100.0-2^31 <= n <= 2^31 - 1nis an integer- Either
xis not zero orn > 0 -10^4 <= x^n <= 10^4
Examples
Input: x = 2.00000, n = 10
Output: 1024.00000
Input: x = 2.10000, n = 3
Output: 9.26100
Input: x = 2.00000, n = -2
Output: 0.25000
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization