Pow(x, n)
Medium · Math · Math · Recursion
Problem
Write myPow(x, n), which returns x raised to the power n, where x is a decimal number and n is a whole number that may be negative.
Do not call a built-in power function (**, pow, math.pow). n can be as large as about two billion in either direction, so multiplying x into the answer |n| times is far too slow: the point of the problem is to need only about log₂ |n| multiplications.
A negative exponent means a reciprocal: x^-n = 1 / x^n. Answers are checked to about six significant digits, since floating-point arithmetic rounds.
Examples
Input: x = 2.0, n = 10 Output: 1024.0
10 is binary 1010, so 2^10 = 2^8 · 2^2 = 256 · 4. Squaring 2 three times gives 2^2, 2^4 and 2^8, and two of them are multiplied in.
Input: x = 2.1, n = 3 Output: 9.261
2.1 · 2.1 · 2.1 = 9.261 (the output may show a tiny rounding error such as 9.261000000000001).
Input: x = 2.0, n = -2 Output: 0.25
2^-2 = 1 / 2^2 = 1 / 4.
Constraints
- -100.0 < x < 100.0
- -2^31 <= n <= 2^31 - 1
- either x is not 0 or n > 0
- -10^4 <= x^n <= 10^4
Approaches
- Baseline: multiply |n| times — time O(|n|), space O(1)
Follow-up
The same squaring loop works for anything you can multiply associatively: modular powers a^b mod m (the core of RSA), 2×2 matrices (the n-th Fibonacci number in O(log n)), and permutations. The use cases below try three of them.
Related problems
Start free on Cariara · Coding problems · System design studio
