# 50. Pow(x, n)

## 1.問題

* 實作pow(x, n)

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LZmPWILgNsNBaGYah8J%2F-LZmPwZoREZLuQpjKuP5%2Fimage.png?alt=media\&token=eaf9e328-6e17-41f7-9ec3-248870261adc)

## 2.想法 <a href="#id-2-xiang-fa" id="id-2-xiang-fa"></a>

* 提問
  * n, x的範圍
* function header, parameter
* test input
* 說明想法
  * 次方的base case為n = 0, 結果為1
  * n > 0
    * n為奇數時則結果為x \* pow(x, n - 1) \* pow(x, n - 1)

      n為偶數時則結果為 pow(x, n - 1) \* pow(x, n - 1)
  * n < 0
    * n為奇數時則結果為1 / x \* pow(x, n - 1) \* pow(x, n - 1)
* 測試計算複雜度

## **3.程式碼** <a href="#id-3-cheng-shi" id="id-3-cheng-shi"></a>

```
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) {
            return 1;
        }

        double half = myPow(x, n / 2);
        
        
        //n is an even and postitive number
        if (n % 2 == 0) {
            return half * half;    
        } 
        
        //n is a positive number
        if (n > 0) {
            return half * half * x;
        }
        //n is a negative number
        return half * half / x;
        
    }
};
```