47. Pow(x, n)

MediumMath

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Examples

Example 1

Input: x = 2.00000, n = 10

Output: 1024.0

Explanation: Multiplying 2 by itself 10 times gives 2^10 = 1024.

Example 2

Input: x = 2.00000, n = -2

Output: 0.25

Explanation: A negative power means taking the reciprocal: 2^-2 = 1 / 2^2 = 1/4 = 0.25.

Example 3

Input: x = 2.00000, n = 0

Output: 1.0

Explanation: Any number raised to the power 0 is 1.

Constraints

-100.0 < x < 100.0
-2^31 <= n <= 2^31 - 1
n is an integer.
Either x is not zero or n > 0.
-10^4 <= x^n <= 10^4

How to solve Pow(x, n): approach and complexity

Fast (Binary) Exponentiation: time, space.

Square the base repeatedly and multiply it into the result only for the set bits of the exponent. This computes x^n in O(log n) multiplications instead of n. Negative exponents just invert the base first.

Watch it run step by step