50. Pow(x, n)
Implement exponentiation yourself: given a floating-point base x and an integer exponent n, compute and return x raised to the power n — without calling the language's built-in pow.
The exponent may be negative (then the answer is 1 / x^|n|) or zero (the answer is 1), and it can be as large as ±2³¹, so multiplying x by itself n times is far too slow. The intended trick is binary exponentiation: squaring cuts the exponent in half, so about log₂ n multiplications suffice.
The judge prints your returned value rounded to 5 decimal places, so tiny floating-point differences do not matter.
Example 1:
Input: x = 2.0, n = 10
Output: 1024.0
Explanation: 2 multiplied by itself 10 times is 1024 — but squaring gets there in 4 multiplications: 2 → 4 → 16 → 256 → 1024 (256 · 4).
Example 2:
Input: x = 2.1, n = 3
Output: 9.261
Explanation: 2.1 · 2.1 · 2.1 = 9.261.
Example 3:
Input: x = 2.0, n = -2
Output: 0.25
Explanation: A negative exponent inverts: 2^-2 = 1 / 2² = 0.25.
Constraints:
- -100.0 ≤ x ≤ 100.0
- -2³¹ ≤ n ≤ 2³¹ - 1
- x is not 0 when n is negative.
- Do not call the built-in pow / operator**.
Hints:
x^n = (x²)^(n/2) when n is even, and x · (x²)^((n−1)/2) when n is odd — each step halves the exponent, so 2³¹ shrinks to 0 in about 31 steps.
Handle n < 0 by computing the positive power and taking its reciprocal (or by inverting x up front). Careful: in a fixed-width integer, negating the minimum value overflows — hold the exponent in a 64-bit type before flipping its sign.
The iterative form walks the bits of n: keep result and base; whenever the current low bit of n is 1, multiply result by base; square base each step and shift n right.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: x = 2.0, n = 10
Expected output: 1024.00000