> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/06-13-2022.md).

# 06/13/2022

brutal force

notice when n is negative. 

convert n to -n. we need to convert int to long to avoid overflow.

Method : divide and conquer. x^n \* x^n = x^2n. For example, if we have 3 ^ 10, if we know the result of 3^5, we can just use the result to multiply the result so we can save half of the linear time. Noticed the if n is odd, we need to use result \* result \* x.  The base case is when n == 0,we retun 1.0. then we use double half to get the result by recursively calling helper function with x, n / 2. if n is even, we return half \* half. If n is odd, we return half \* half \* x. 

Time O(logn)

Space O(logn)