💯 Daily LeetCode Challenge Day_16 - Pow(x, n)

Explore - LeetCode

---

문제

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]

---

처음 코드

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        var answer = x
        if n > 0 {
            for i in 1..<n{
                answer = answer * x
            }
        }else{
            for i in n..<1 {
                answer = answer * 1/x
            }
        }
        return answer
    }
}

Test case 0.00001 2147483647 에서 Time Limit Exceeded

for 문을 없애야 한다.

Recursion 이용

class Solution {
    func myPow(_ x: Double, _ n: Int) -> Double {
        print(x)
        if n < 0 {
            return 1/x * myPow(1/x, -(n+1))
        }
        if n == 0 { return 1}
        if n == 2 {
            return x*x
        }
        if n%2 == 0 { return myPow(x*x, n/2)}
        else { return x*myPow(x*x,n/2)}
    }
}

 

그냥 for 문을 돌면 2.0000, 100 input 에서 100번을 계산할 것이다.

그러나 위 코드를 사용하면 8 번만에 계산을 완료할 수 있다.

1. 2.0
2. 4.0
3. 16.0
4. 256.0
5. 65536.0
6. 4294967296.0
7. 1.8446744073709552e+19
8. 3.402823669209385e+38