50. Pow(x, n)

Problem Statement

Pattern:

---

Solution

 
static class Solution {
	public static double simplePow(double x, int n) {
		if (n == 0) return 1;
		if (n < 0) return (1 / x) * (simplePow(1 / x, -(n + 1)));
		
		double result = simplePow(x, n - 1);
		return result * x;
	}
	
	public static double myPow(double x, int n) {
		// exit condition
		if (n == 0) return 1;
		if (n < 0) return 1 / x * myPow(1 / x, -(n + 1)); // n=int.minVal -> overflow avoided
		double result = myPow(x, n / 2);
		result *= result;
		if ((n & 1) != 0) result *= x;  // compensate for odd power
		System.out.println(result);
		return result;
	}
	
	public static double myPowIterative(double x, int n) {
		double result = 1;
		
		if (n < 0) {
			n = -(n + 1);   // sign flipped and integer overflow avoided
			x = 1 / x;      
			result *= x;    // compensate for n-1
		}
		
		while (n > 0) {
			// if n is odd for a given x, multiply result by x
			if (n % 2 == 1) result *= x;
			// otherwise continue to square x
			x *= x;
			n /= 2;
		}
		// result always updated in the end cuz final n == 1
		return result;
	}
	
	
}
 
// region MAIN
public static void main(String[] args) {
	// int[] arr = {};
	double x = 2;
	int n = 0;
	double ans = Solution.simplePow(x, n);
	System.out.println(ans);
	System.out.println("\nFAST ANSWER\n");
	double fastAns = Solution.myPow(x, n);
	System.out.println(fastAns);
	System.out.println("\nFASTER ANSWER\n");
	double fasterAns = Solution.myPowIterative(x, n);
	System.out.println(fasterAns);
}
 

Notes

• Quck Explanation :Binary Exponentiation - YouTube
• for n<0 if n = Integer.MIN_VALUE, then n = -n will cause an overflow, since MAX_VALUE - MIN_VALUE = -1