codejump
MediumPro challengePythonJavaScriptTypeScript

Math — Pow(x, n) by Squaring

AlgorithmsMathBit ManipulationDivide and Conquer

solve(x, n) — return x raised to the integer power n (n can be negative or
zero, |n| up to 2^31). Do not use **, Math.pow or pow(). Multiplying x by itself
n times is O(n) and far too slow for n = 2^31.

Exponentiation by squaring needs only O(log n) multiplications. Write n in binary:
x^13 = x^8 · x^4 · x^1. Keep base squaring itself at each step, and multiply it into
the result whenever the current lowest bit of n is set. A negative exponent is the
reciprocal of the positive one.

Examples

solve(2, 10)   → 1024
solve(2, -2)   → 0.25
solve(-2, 3)   → -8
solve(2, 0)    → 1

Sample tests

Test #1Positive exponent
Input: [2,10]
Output: 1024
Test #2Negative exponent
Input: [2,-2]
Output: 0.25
Test #3Negative base, odd power
Input: [-2,3]
Output: -8
← All challenges