Leetcode 50: Pow(x, n)

 

1. Problem Statement (Simple Explanation):

You must implement:

pow(x, n) = xn

where:

• x is a double (-100 < x < 100).

• n is a 32-bit signed integer (-231 <= n <= 231 - 1).

• Either x != 0 or n > 0.

• Result xn is guaranteed to be in range [-104, 104].

You should handle negative exponents:

• x(-n) = 1 / (xn)

2. Examples:

Example 1:

Input: x = 2.00000, n = 10

210 = 1024

Output: 1024.00000

Example 2:

Input:

x = 2.10000, n = 3

2.13 = 2.1 * 2.1 * 2.1 = 9.261

Output: 9.26100

Example 3:

Input:

x = 2.00000, n = -2

2(-2) = 1 / 22 = 1 / 4 = 0.25

Output: 0.25000

3. Approach – Fast Exponentiation (Binary Exponentiation):

We want an efficient algorithm, better than multiplying x |n| times.

Key Idea:

Use Exponentiation by Squaring:

• For integer n:

• If n == 0: return 1

• If n is even:

• xn = (x2)(n/2)

• If n is odd:

• xn = x*x(n-1)

We can implement this iteratively using the binary representation of n:

• Let n > 0.

• Keep a result initialized to 1.

• While n > 0:

• If n is odd → multiply result by x.

• Square x (x *= x).

• Shift n right by 1 (n /= 2).

For negative n, use:

• xn = 1 / x(-n).

Be careful with n = Integer.MIN_VALUE (-231): -n would overflow a 32-bit int.
So cast to a 64-bit integer (long in Java/C++), or use long long / long in other languages.

Pseudo-code:

Complexity:

• Time: O(log|n|) – each step halves exponent.

• Space: O(1) – just a few variables.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: