LeetCode Solution 50 - Pow(x, n)

 Problem Statement

Given two numbers, x and n, where x is a floating-point number and n is an integer, implement a function to calculate x raised to the power n (x^n).

Constraints:

• -100.0 < x < 100.0
• -2³¹ <= n <= 2³¹ - 1
• n is an integer
• Results are within a 32-bit floating point range

---

Optimal Approach: Binary Exponentiation (Fast Power Method)

Instead of iterating n times (which takes O(n) time), we can reduce the number of multiplications by using a divide-and-conquer strategy:

1. If n is even, then: $x^n = (x^{n/2})^2$
2. If n is odd, then: $x^n = x \times x^{n-1}$
3. If n is negative, then: $x^n = 1 / x^{-n}$

Advantages of this approach:

• Time Complexity: O(log n) (instead of O(n) for naive approach)
• Space Complexity: O(1) (iterative approach) or O(log n) (recursive approach)

---

LeetCode-Compatible C++ Solution (Iterative)

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;  // Use long long to handle edge case when n = INT_MIN
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double result = 1;
        while (N) {
            if (N % 2 == 1) {  // If n is odd
                result *= x;
            }
            x *= x;  // Square x
            N /= 2;  // Divide exponent by 2
        }
        return result;
    }
};

Step-by-Step Explanation:

1. Convert n to a long long to prevent overflow (for INT_MIN case).
2. If n is negative, invert x and take the absolute value of n.
3. Initialize result = 1.
4. Run a loop while n > 0:
   • If n is odd, multiply result by x.
   • Square x and halve n.
5. Return result.

---

Dry Run / Execution Steps

Input: x = 2.0, n = 10

Step	n	x	result
1	10	2	1
2	5	4	1
3	2	16	4
4	1	256	4
5	0	65536	1024

Output: 1024.0

---

Alternative Approaches

1. Brute Force (O(n) Time Complexity)

class Solution {
public:
    double myPow(double x, int n) {
        double result = 1;
        for (int i = 0; i < abs(n); i++) {
            result *= x;
        }
        return (n < 0) ? (1 / result) : result;
    }
};

Why Not?

• Slow for large n (e.g., n = 10⁹ takes too long).
• O(n) time complexity.

2. Recursive Approach (O(log n) Time Complexity)

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        double half = myPow(x, n / 2);
        return (n % 2 == 0) ? half * half : half * half * x;
    }
};

Why Not?

• Uses extra stack space (O(log n) recursion depth).
• May cause stack overflow for large values of n.

---

Best Solution & Comparison

Approach	Time Complexity	Space Complexity	Why?
Iterative (Best)	O(log n)	O(1)	Fastest, no extra memory
Recursive	O(log n)	O(log n)	Extra stack space used
Brute Force	O(n)	O(1)	Too slow for large n

Why is Iterative Best?

• Avoids recursion overhead.
• Handles edge cases like INT_MIN correctly.
• Optimal time complexity O(log n) with O(1) space.

---

Complexity Analysis

Approach	Time Complexity	Space Complexity
Brute Force	O(n)	O(1)
Recursive	O(log n)	O(log n)
Iterative (Best)	O(log n)	O(1)

---

Conclusion

• The iterative approach using Binary Exponentiation is the best.
• Handles negative exponents properly.
• Optimized to run in O(log n) time with O(1) space.
• Used in real-world applications like cryptography, scientific computing, and finance.

---

Similar Problems for Practice:

1. Sqrt(x) (LeetCode 69) – Similar approach using binary search.
2. Super Pow (LeetCode 372) – Extended version of power function.
3. Modular Exponentiation – Used in cryptographic algorithms.

📢 Explore More on My Blog:

• 🔗 Binary Search: Best Practices & Implementation
• 🔗 Understanding Recursion: A Beginner's Guide
• 🔗 Optimizing Algorithms: How to Reduce Time Complexity

💡 Follow for more coding insights & LeetCode solutions! 🚀