Pow(x, n)

Description

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

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/22 = 1/4 = 0.25

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n is an integer.
• Either x is not zero or n > 0.
• -104 <= xn <= 104

Approach

• We have two conditions one with odd and one with even
  

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

1. Brute Force Solution

Intuition:
Multiply $x$ by itself $n$ times. If $n$ is negative, invert $x$ ($x=1/x$) and convert $n$ to positive.

Complexity:

• Time Complexity: $O(N)$ — Multiplies $N$ times. (Causes TLE on LeetCode)
• Space Complexity: $O(1)$

class Solution {
    public double myPow(double x, int n) {
        long N = n; // Cast to long to handle Integer.MIN_VALUE overflow
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
 
        double ans = 1.0;
        for (long i = 0; i < N; i++) {
            ans = ans * x;
        }
        return ans;
    }
}

---

2. Most Optimized Solution (Binary Exponentiation)

Intuition:
Instead of multiplying one by one, halve the exponent at every step:

• If exponent $N$ is odd, multiply the current base $x$ into the result res.
• Square the base ($x=x\times x$) and halve the power ($N=N/2$) in every iteration.

Key Rule to Remember:

“If power is odd, extract one $x$ into res. Always square the base and half the power.”

Complexity:

• Time Complexity: $O(\log N)$ — Divides $N$ by 2 in every iteration.
• Space Complexity: $O(1)$ — Iterative approach uses $O(1)$ extra memory.

class Solution {
    public double myPow(double x, int n) {
        long N = n; // Handles Integer.MIN_VALUE (-2^31) edge case safely
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
 
        double res = 1.0;
        while (N > 0) {
            // If power is odd, accumulate x into result
            if (N % 2 == 1) {
                res *= x;
            }
 
            // Square the base & halve the exponent
            x *= x;
            N /= 2;
        }
 
        return res;
    }
}
 

In your Java solution for Pow(x, n), long N is used to prevent integer overflow when $n$ is negative.

---

**1. The Problem with Integer.MIN_VALUE**

In Java, a standard 32-bit signed int ranges from:

• Minimum value: $-2^{31}=-2,147,483,648$
• Maximum value: $2^{31}-1=2,147,483,647$

Notice that the absolute value of the minimum integer ($2,147,483,648$) is $1$ greater than the maximum positive integer ($2,147,483,647$).

---

2. What happens if you don’t use long?

If $n=-2147483648$ and you try to convert it to positive using a standard int:

int N = n;
if (n < 0) {
    N = -N; // Overflow! -(-2147483648) exceeds Integer.MAX_VALUE
}
 

Because of integer overflow in Java, -(-2147483648) wraps around and remains -2147483648. As a result, the while (N > 0) loop condition immediately evaluates to false, returning 1 instead of computing the correct answer.

---

3. How long Fixes It

By storing $n$ in a 64-bit long variable (long N = n;), the variable can easily represent values up to $2^{63}-1\approx 9.22\times 10^{18}$. Negating $N$ (N = -N;) safely converts $-2,147,483,648$ to $+2,147,483,648$ without any overflow.