Pow(x, n) (Java)

LeetCode:

Implement pow(x, n).

Solution: Binary Search

	This is a simple question, however the format is very important
	x^n={
	x^n= 1.0 if n==0,
	x^(n/2)* x^(n/2) if n!=0 and n is even,
	x^|n/2| * x^|n/2| * x if n>0 and n is odd,
	x^|n/2| * x^|n/2| * x^-1 if n<0 and n is odd,
	}
	Once it got this formula, then, the code become relatively easy.
	the time complexity is O(lgn) hint: (half=pow(x,n/2))
	public class Solution {
	public double pow(double x, int n) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	// n is even , then x^n=x^n/2*x^n/2
	// n>0 and n is odd, x^n=x^n/2 * x^n/2 *x
	// n<0 and n is odd, x^n=x^n/2 *x^n/2 *x^-1
	if (n==0) {
	return 1.0;
	}
	double half=pow(x, n/2);
	if (n%2==0){
	return half*half;
	}
	else if (n>0){
	return half*half*x;
	}
	else {
	return half*half* (1/x);
	}
	}
	}

view raw power(x, n).java hosted with ❤ by GitHub