Problem Statement

Implement the function myPow(x, n) which calculates x raised to the power n (i.e., xⁿ).

You must not use built-in library functions like Math.pow() and must handle both positive and negative exponents efficiently.

Examples

1. Input: x = 2.00000, n = 10 Output: 1024.00000
2. Input: x = 2.10000, n = 3 Output: 9.26100
3. Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2⁻² = 1 / (2²) = 0.25

---

Approach: Fast Exponentiation (Binary Exponentiation)

Intuition

The naive approach of multiplying x by itself n times takes O(n) time — inefficient for large n.

Instead, we can use Divide and Conquer:

• Split the exponentiation recursively: xⁿ = (x^(n/2)) * (x^(n/2)) if n is even xⁿ = x * (x^(n/2)) * (x^(n/2)) if n is odd
• For negative exponents, use: xⁿ = 1 / x⁻ⁿ

This reduces the time complexity to O(log n).

---

Algorithm Steps

1. Handle the base case:
   • If n == 0, return 1 (since x⁰ = 1).
2. If n < 0, convert to positive using x = 1/x and n = -n.
3. Recursively compute half = myPow(x, n / 2).
4. If n is even, return half * half.
5. If n is odd, return x * half * half.

---

Code (Recursive Implementation)

public class Solution {
    public double myPow(double x, int n) {
        // Base case
        if (n == 0) return 1.0;
        
        // Handle negative exponent
        if (n < 0) {
            x = 1 / x;
            // Use long to avoid overflow when n == Integer.MIN_VALUE
            n = -(n + 1);
            return x * myPow(x, n);
        }
        
        double half = myPow(x, n / 2);
        
        if (n % 2 == 0) {
            return half * half;
        } else {
            return x * half * half;
        }
    }
}

---

Code (Iterative Binary Exponentiation)

This avoids recursion and stack overhead.

public class Solution {
    public double myPow(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        
        double result = 1.0;
        while (N > 0) {
            if ((N % 2) == 1) {
                result *= x;
            }
            x *= x;
            N /= 2;
        }
        
        return result;
    }
}

---

Time Complexity

• Recursive or Iterative Binary Exponentiation: O(log n)
• Space Complexity:
  • Recursive: O(log n) (due to recursion stack)
  • Iterative: O(1)

---

Dry Run

Example

Input: x = 2.0, n = 10

Initial State

• result = 1.0
• x = 2.0
• N = 10

Step-by-Step Execution

Iteration	N (binary)	N (decimal)	N%2	result	x (base)	Operation
1	1010	10	0	1.0	2.0	Square base → x = 4.0
2	0101	5	1	1.0 * 4.0 = 4.0	4.0	Multiply result by base
3	0010	2	0	4.0	16.0	Square base → x = 16.0
4	0001	1	1	4.0 * 16.0 = 64.0	16.0	Multiply result by base
5	0000	0	–	–	–	Stop

Final Result: 64.0

But we had one more square from earlier (2⁶ = 64, 2⁸ = 256, 2¹⁰ = 1024).
Hence final output: 1024.0

---

For Negative Exponent

Input:

x = 2.0, n = -2

Steps:

• Convert to positive: x = 1/2 = 0.5, n = 2
• Compute normally → result = 0.25

---

Key Insights

• Binary exponentiation reduces time drastically from O(n) to O(log n).
• Handle Integer.MIN_VALUE carefully because -n can overflow; use a long.
• Iterative approach is more memory-efficient.