Data structures and algorithms
## Pow(x, n)

###### Example 1:

###### Example 2:

###### Example 3:

###### Constraints:

##### Solution:

###### Time/Space Complexity:

###### Explanation:

comments powered by Disqus

**Pow(x, n):**
Implement `pow(x, n)`

, which calculates `x`

raised to the power `n`

(i.e., `x^n`

).

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

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

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

`-100.0 < x < 100.0`

`-2^31 <= n <= 2^31-1`

`n`

is an integer.`-10^4 <= x^n <= 10^4`

Try this Problem on your own or check similar problems:

```
class Solution {
public double myPow(double x, int n) {
if(n == 0) return 1.0;
if(n < 0) return 1/pow(x, -n);
return pow(x, n);
}
private double pow(double x, int n){
if(n == 0) return 1;
double halfPow = pow(x, n / 2);
if(n % 2 == 0){
return halfPow * halfPow;
}
return halfPow * halfPow * x;
}
}
```

- Time Complexity:
*O(logn)* - Space Complexity:
*O(logn)*

The time and space complexity is logarithmic since we can ask ourselves how many times can we half `n`

(it’s `logn`

times), space complexity accounts for the recursion stack. The base case is if `n=0`

we know that `x^0=1`

so we return `1`

. For negative numbers we calculate the reciprocate value since `x^-y = 1/x^y`

. Note that we can formulate recursive relation for `pow`

operation `pow(x, n) = pow(x^n/2) * pow(x^n/2)`

for even `n`

(e.g. `x^4 = x^2 * x^2`

), while for odd `n`

we have the following `pow(x, n) = pow(x^n/2) * pow(x^n/2) * x`

(e.g. `x^5 = x^2 * x^2 * x`

).

Don’t settle for anything less than the crown. Join our newsletter and become the King of Interviews! **Click here** to join now and get the latest updates.