Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Last active August 29, 2015 13:56
Show Gist options
  • Save Jeffwan/8852911 to your computer and use it in GitHub Desktop.
Save Jeffwan/8852911 to your computer and use it in GitHub Desktop.
Pow(x, n) @leetcode
package leetcode.binarySearch;
/**
* Solution: BinarySearch
*
* Tricky:
* 1. n could be negative.
* 2. n cound be Integer.MIN_VALUE(-2147483648) and Integer.MAX_VALUE(2147483647)
* 3. handle n == 0, 1 as terminating condition.
*
* @author jeffwan
* @date Mar 10, 2014
*/
public class Pow {
public double pow (double x, int n) {
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
if (n < 0) {
// Value of pow(x, Integer.MIN_VALUE)? == pow(x, Integer.MAX_VALUE) * x
if ( n == Integer.MIN_VALUE) {
return 1 / (pow(x, Integer.MAX_VALUE) * x);
} else {
return 1 / pow(x, -n);
}
}
// BinarySearch Thought
double half = pow(x, n / 2);
if (n % 2 == 1) {
return half * half * x;
} else {
return half * half;
}
}
// Brute Force
public double pow2 (double x, int n) {
double temp = x;
for (int i = 1 ; i<= n; i++) {
x *= temp ;
}
return x;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment