> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/powx-n.md).

# Pow(x, n)

https\://leetcode.com/problems/powx-n/description/

> Implement [pow(x,n)](http://www.cplusplus.com/reference/valarray/pow/)

## Thoughts

分治，比如2^9分成2^4 \* 2^4 \* 2，2^4再分成2^2\*2^2直到n == 1。n是奇数时还有个额外的x要乘，n为负数时用且n为奇数时做额外除x。n为INT\_MIN时可能导致的 \*溢出问题，因此不建议当n < 0时让n = -n, x = 1/ x的方法，而是直接让pow(x / 2) / x 比较好。

## Code

```cpp
/*
 * @lc app=leetcode id=50 lang=cpp
 *
 * [50] Pow(x, n)
 */
class Solution {
public:
    double myPow(double x, int n) {
        if (n == 0) return 1;
        double res = myPow(x, n / 2);
        res *= res;
        if (n % 2 == 0) return res;
        if (n < 0) return res / x;
        return res * x;
    }
};


```

## Analysis

Errors:\
1\. n = min\_value溢出

时间复杂度O(lgN), 空间O(1).