Problem

Implement pow(x, n), which calculates x raised to the power n (i.e., x^n).

Examples

Example 1:

1
2

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

1
2

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

1
2
3

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/2^2 = 1/4 = 0.25

Solution

Method 1 - Normal Multiplication

Code

1
2
3
4
5
6
7
8

public double myPow(double x, int n) {
    double ans = 1;
    for(int i = 0; i < n; i++){
	    ans = ans * x; 
    }

    return ans;
}

Method 2 - Divide and Conquer

When we have an even exponent, for eg. 2^10, we have ans = 2^5 * 2^5. Likewise, when we have odd we have 2^11 = 2 * 2^5 * 2^5. There is 1 minor change we can do, using a^2n = (a^2)^n = (a*a)^n.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public double pow(double x, int n) {
	if(n == 0) {return 1;}
	if (x == 0) {return 0;}
	
	if(n<0){
		n = -n;
		x = 1/x;
	}
	
	int ans = pow(x*x, n/2);
	
	return (n%2 == 0) ? ans : x*ans;
}

### Method 3 - Using Bits

Implement Exponentiation using Bitwise Operator