LeetCode Q 50 - Pow(x, n)

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

Example 1: Input: 2.00000, 10 ; Output: 1024.00000
Example 2: Input: 2.10000, 3 ; Output: 9.26100
Example 3: Input: 2.00000, -2 ; Output: 0.25000

Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range [−2^31, 2^31 − 1]

Solution

Basic idea is to utilize simple multiplication. We do x x x x … n times. This approach has a potential to cause time limit exceeds, when n is very large.
Instead we can utilize redouble the x, say

for n = 2, we do x * x
for n = 4, we do x x, then do (x x) (x x)…
if n is odd, then multipy an additional tempX.
Next, we will solve this question recursively and iteratively

Solution 1: TLE

If we solve this problem like solving multiplication, then TLE may happen.

Code: Wrong Version

public double myPow(double x, int n) {
  if (n == 0) return 1;

  if (n < 0) { 
    x = 1 / x;
    if (n == Integer.MIN_VALUE) 
      return x * myPow(x, Integer.MAX_VALUE);
    n = -n;
  }

  double res = x;
  int multiplication = 1;
  while (multiplication + multiplication < n) {
    res *= res; multiplication *= 2;
  }

  return res * myPow(x, n - multiplication);
}

Solution 2: Recursion Method

Code: Recursive Method

public double myPow(double x, int n) {
  if (n == 0) return 1.0;
  
  if (n < 0) {
    x = 1 / x;
    if (n == Integer.MIN_VALUE) 
      return x * myPow(x, Integer.MAX_VALUE);
    n = -n;
  }

  return n % 2 == 0 ? myPow(x * x, n / 2) : x * myPow(x * x, n / 2);
}

Solution 3: Iteration Method

Code: Iterative Method

public double myPow(double x, int n) {
  if (n == 0) return 1.0;

  if (n < 0) {
    x = 1 / x;
    if (n == Integer.MIN_VALUE) 
      return x * myPow(x, Integer.MAX_VALUE);
    n = -n;
  }

  double ans = 1;
  while (n != 0) {
    if (n % 2 == 1) ans *= x;
    x *= x;
    n /= 2;
  }
  
  return ans;
}

Reprint policy