[LeetCode] Pow(x, n)

문제

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10 Output: 1024.00000

Example 2:

Input: 2.10000, 3 Output: 9.26100

Example 3:

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

Note:

• -100.0 < x < 100.0
• n is a 32-bit signed integer, within the range [−231, 231 − 1]

Approach

return Pow(x, n)

빠른 계산을 위해 재귀를 활용해 n%2 == 0일땐 pow(x, n/2) * pow(x, n/2)로 나눠 계산하고

아닐땐 x * pow(x, n-1) 나눠 계산한다.

그리고 n이 0일땐 1, 1일땐 x, -1일땐 1/x를 리턴한다.

시간복잡도는 O(nlogn)

 

Code 

https://github.com/chi3236/algorithm/blob/master/LeetCode_Pow(x%2Cn).cpp

chi3236/algorithm