Fast Power (xⁿ)

Difficulty: Easy · Topic: Divide & conquer

Implement pow(x, n) — x raised to the integer power n (which may be negative). Use exponentiation by squaring: xⁿ = (x²)^(n/2), halving the exponent each step for O(log n) multiplications.

Examples

my_pow(2, 10)
→ 1024

2^10.

my_pow(2, -2)
→ 0.25

Negative exponent → reciprocal.

Target complexity: time O(log n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.