LeetCode Problem

Problem Description

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Examples

Input: x = 2.00000, n = 10
Output: 1024.00000

Input: x = 2.10000, n = 3
Output: 9.26100

Input: x = 2.00000, n = -2
Output: 0.25000

Constraints

-100.0 < x < 100.0
-2^31 <= n <= 2^31-1
n is an integer.
-10^4 <= x^n <= 10^4

Follow-up

Approach to Solve

Use a recursive approach with binary exponentiation to calculate the power of x to the n.

Code Implementation

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0:
            return 1
        if n < 0:
            return 1 / self.myPow(x, -n)
        half = self.myPow(x, n // 2)
        if n % 2 == 0:
            return half * half
        else:
            return half * half * x

class Solution {
    public double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            // Handle potential integer overflow for n = Integer.MIN_VALUE
            return (n == Integer.MIN_VALUE) ? 1 / (x * myPow(x, -(n + 1))) : 1 / myPow(x, -n);
        }
        double half = myPow(x, n / 2);
        return (n % 2 == 0) ? half * half : half * half * x;
    }

class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        if (n < 0) {
            // Handle potential integer overflow for n = INT_MIN
            return (n == INT_MIN) ? 1 / (x * myPow(x, -(n + 1))) : 1 / myPow(x, -n);
        }
        double half = myPow(x, n / 2);
        return (n % 2 == 0) ? half * half : half * half * x;
    }

Explanation

This solution uses a recursive approach with binary exponentiation to calculate the power of x to the n. Here's a detailed explanation of the algorithm:

If n is 0, return 1 (base case).
If n is negative, we handle it by computing the reciprocal of x^(-n).
For positive n, we use the binary exponentiation technique: a. Recursively calculate half = x^(n/2). b. If n is even, return half * half. c. If n is odd, return half * half * x.
The recursion continues, effectively dividing the problem in half each time.

The time complexity is O(log n) due to the recursive halving of n. The space complexity is O(log n) for the recursive call stack.

Note: The Java and C++ implementations include additional handling for the edge case where n is the minimum possible integer value (INT_MIN) to prevent overflow when negating n.

Complexity

Time Complexity: O(log n)
Space Complexity: O(log n)

LeetSolved

Pow(x, n)