050.Pow(x, n)

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
10
11
12
8.88023
3
34.00515
-3
0.00001
2147483647
1.00000
2147483647
1.00000
-2147483648
2.00000
-2147483648

Solution 1: TLE

Brute force is not working. 

1
2
3
4
5
6
7
8
9
10
11
public double myPow(double x, int n) {
    if (n == 0) return (double)1;
    double result = 1;
    boolean neg = n < 0? true : false;
    n = Math.abs(n);
    while (n > 0) {
        result *= x;
        n--;
    }
    return neg? 1 / result : result;
}

Solution 2: accepted 24ms

Binary method. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public double myPow(double x, int n) {
  if (n == 0) 
      return (double)1;
  double result = 1;
  boolean isNegative = n < 0;
  if (n == Integer.MIN_VALUE) {
      result = x;
      n = Integer.MAX_VALUE;
  }
  n = n < 0? -n : n;
  while (n > 0) {
    int factor = 1;
    double base = x;
    while (n / 2 >= factor) { // n >= factor * 2 may cause overflow if n is the max or min int
      factor *= 2;
      base *= base;
    }
    result *= base;
    n -= factor;
  }
  return isNegative? 1 / result : result;
}
Alternative: accepted 20ms

Use long to avoid MAX and MIN checks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public double myPow(double x, int n) {
  if (n == 0) 
      return (double)1;
  double result = 1;
  boolean isNegative = n < 0;
  long ln = (long)n;
  ln = ln < 0? -ln: ln;
  while (ln > 0) {
    long factor = 1;  // int will cause factor = 0 (overflow) when n = MIN_VALUE
    double base = x;
    while (ln / 2 >= factor) {
      factor *= 2;
      base *= base;
    }
    result *= base;
    ln -= factor;
  }
  return isNegative? 1 / result : result;
}