## [50\. Pow(x, n)](https://leetcode.com/problems/powx-n/)

Implement [pow(x, n)](http://www.cplusplus.com/reference/valarray/pow/), which calculates `x` raised to the power `n` (i.e., `xn`).

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

**Constraints:**

- `-100.0 < x < 100.0`
- `-231 <= n <= 231-1`
- `n` is an integer.
- Either `x` is not zero or `n > 0`.
- `-104 <= xn <= 104`

class Solution {
public:
    double myPow(double x, int n) {
        if(n == 0) return 1;
        double half = myPow(x, n / 2);
        if(n % 2 == 0) return half * half;
        // 如果不是偶數的話
        return n > 0 ? half * half * x : half * half / x;
    }
};

:::success
- 時間複雜度：$O(\log N)$
- 空間複雜度：$O(1)$
:::