Pow(x, n)

Implement pow(x, n) which calculates x raised to the power n. A naive loop is too slow for large |n|.

Function signature

func MyPow(x float64, n int) float64

Inputs / outputs

• x: base.
• n: exponent (can be negative).
• Return: x^n.

Example

2^10 = 1024
2^-2 = 0.25

Constraints

• -2^31 <= n <= 2^31 - 1

Core idea (near-solution)

Use binary (fast) exponentiation. Repeatedly square the base and use the bits of n to decide when to multiply into the result.

Invariant: after processing the low bits of n, res equals x^(original bits processed).

Algorithm (step-by-step)

1. Convert n to int64 to handle INT_MIN safely.
2. If n < 0, set x = 1/x and n = -n.
3. Initialize result = 1.
4. While n > 0:
   • If n is odd, result *= x.
   • x *= x, n >>= 1.
5. Return result.

Correctness sketch

• Invariant: after processing the low bits of n, res equals x^(original bits processed).
• The formula/transform follows from number properties or monotonicity.
• Each iteration preserves the mathematical invariant.
• Thus the computed value matches the definition of the problem.

Trace (hand walkthrough)

Example input:
2^10 = 1024
2^-2 = 0.25

Walk:
- 2^10: n=10 even -> x=4; n=5 odd -> res=4, x=16; n=2 -> x=256; n=1 -> res=1024
- 2^-2: invert x=0.5, n=2 -> x=0.25, n=1 -> res=0.25

Pitfalls to avoid

• Overflow when negating INT_MIN (use int64).
• Forgetting to invert x for negative exponents.

Complexity

• Time: O(log |n|).
• Extra space: O(1).

Implementation notes (Go)

• Use int64 for the exponent to safely negate n.