**Pow(x, n)**

#### Description

Implement `pow(x, n)`

, which calculates x raised to the power n (x^{n}).

#### Example

1 | Example 1: |

#### Solution

The basic thought of this problem is `Divide & Conquer`

. We can divide it into two halves and then calculate it. For example1 `n = 10`

, then we can have 2^{10} = 2^{5} * 2^{5}, next we calculate 2^{2} and 2^{3}, but wait a second, when n is odd, we need to calculat twice, why can’t we just calculate 2^{2}, and then 2^{2} * 2^{2} * 2, so based on this, we can come up with the following algorithm. This is just for `x >= 0`

, if `x < 0`

, we need to pay a little more attention.

#### Algorithm

##### My algorithm

*Python*

1 | def myPow(self, x, n): |

This is my algorithm, a little long, but the basic idea is correct. Let’s see a more concise one.

##### Concise algorithm

*Python*

1 | def myPow(self, x, n): |

This one is really elegant and concise…

##### Complexity

Time Complexity: `O(log(n))`

.

Space Complexity: `O(1)`

.