244. Fast Power
A physics simulator needs to scale a signal by the same gain factor many times in a row. Implement fastPower(x, n), which returns x raised to the integer power n as a floating-point number.
The exponent n can be negative, in which case the result is 1 divided by x^|n|, and it can be as large in magnitude as 2^31. A loop that multiplies x by itself n times is far too slow for such values, so use exponentiation by squaring: halve the exponent at every step for O(log |n|) time and O(1) extra space.
Watch out for the most negative 32-bit exponent: negating -2147483648 does not fit in a 32-bit int in Java or C++. Any answer within an absolute error of 1e-6 is accepted. Inputs are chosen so that the exact result never exceeds 10^4 in absolute value, and x is never 0 when n is negative. Also, x^0 = 1 for every x, including 0.
Example 1
- Input:
- x = 1.5, n = 7
- Output:
- 17.0859375
- Explanation:
1.5 multiplied by itself seven times is 17.0859375.
Example 2
- Input:
- x = 0.5, n = -13
- Output:
- 8192
- Explanation:
A negative exponent inverts the base: 0.5^-13 equals 2^13 = 8192.
Example 3
- Input:
- x = -1.1, n = 5
- Output:
- -1.6105100000000006
- Explanation:
An odd power of a negative base stays negative: (-1.1)^5 = -1.61051.
Constraints
-100.0 ≤ x ≤ 100.0
-231 ≤ n ≤ 231 - 1
If n < 0 then x ≠ 0.
The true value of x^n satisfies |x^n| ≤ 104.
How this problem is judged
- Answers
- Numbers are accepted within a tolerance of 1.0E-6: |answer - expected| <= 1.0E-6 x max(1, |expected|).
- Tolerance
0.000001
Expected complexity
- Time
- O(log |n|)
- Space
- O(1)