LeetCode //C - 50. Pow(x, n)

50. Pow(x, n)

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

Example 1:

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

Example 2:

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

Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: $2^{-2}=1/2^2=1/4=0.25$

Constraints:

• -100.0 < x < 100.0
• $-2^{31}<=n<=2^{31}-1$
• n is an integer.
• Either x is not zero or n > 0.
• $-10^4<=x^n<=10^4$

From: LeetCode
Link: 50. Pow(x, n)

---

Solution:

Ideas：

1. The powHelper function recursively calculates the power for a non-negative exponent.
2. For the case when n is negative, it calculates the power for the positive value of n and then returns the reciprocal of the result.
3. The isNegative flag is used to check if the original n was negative.
4. Special care is taken to avoid overflow when converting a negative n to its positive counterpart, especially important when n is INT_MIN.

Code:

double myPow(double x, int n) {
    // Helper function to calculate power for non-negative exponent
    double powHelper(double x, unsigned int n) {
        if (n == 0) return 1;
        double half = powHelper(x, n / 2);
        if (n % 2 == 0) 
            return half * half;
        else 
            return half * half * x;
    }

    // Handling the case when n is negative
    bool isNegative = false;
    unsigned int positiveN = n;
    if (n < 0) {
        isNegative = true;
        positiveN = -((unsigned int)n); // Convert to positive, handle overflow
    }

    double result = powHelper(x, positiveN);

    // If n is negative, return the reciprocal
    return isNegative ? 1 / result : result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24