# [LeetCode 50] Pow(x, N)

### Question

Implement pow(x, n).

### Stats

 Frequency 5 Difficulty 3 Adjusted Difficulty 3 Time to use ----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Solution

This question have many interesting solutions. The bottom line is solving in O(lgn) time.

First approach, we can keep cumulating power(x, 2 ^ n).

Second approach, divide and conquer which is explained in this blog and this code.

### My code

code 1, divide and conquer

``````public class Solution {
public double pow(double x, int n) {
if (n == 0) {
return 1;
} else if (n < 0) {
if (n == Integer.MIN_VALUE) {
// since the negate of Integer.MIN_VALUE overflows...
return (1 / x) / pow(x, Integer.MAX_VALUE);
} else {
return 1 / pow(x, -1 * n);
}
} else if (n % 2 == 0) {
return pow(x * x, n / 2);
} else {
return x * pow(x, n - 1);
}
}
}
``````

code 2, divide and conquer

``````public double pow(double x, int n) {
if (n < 0) return 1 / helper(x, 0-n);
else return helper(x, n);
}

private double helper(double x, int n) {
if (n == 0) return 1;
double half = helper(x, n / 2);
return n % 2 == 1 ? x * half * half : half * half;
}
``````

code 3

``````public double pow(double x, int n) {
if (n == 0) return 1;
if (n == 2) return x * x;

if (n % 2 == 0) return pow(pow(x, n / 2), 2);
else if (n > 0) return x * pow(pow(x, n / 2), 2);
else return 1 / x * pow(pow(x, n / 2), 2);
}
``````