Loop

Pow(x, n)

mediumMath & Geometryfast exponentiation by squaringSolve on LeetCode#50

Part of Practice: Digits & Points

Implement pow(x, n): raise a floating-point number x to an integer power n, without using the built-in power function. The exponent can be negative, and it ranges over the full 32-bit integer range, so multiplying x by itself n times — up to two billion multiplications — is far too slow. The expected solution uses O(log n) multiplications.

Examples

Input:
x = 2.0, n = 10
Output:
1024.0
Input:
x = 2.1, n = 3
Output:
9.261
Input:
x = 2.0, n = -2
Output:
0.25

A negative exponent means take the reciprocal: 2^-2 = 1 / (2^2) = 1/4.

Hints

One at a time — struggle first, peek second.

Your thinking space — verify on LeetCode, then mark it.