Pow(x, n)[M,Math,Recursion]

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

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

 

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000

Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100

Example 3:

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

 

Constraints:

• -100.0 < x < 100.0
• -231 <= n <= 231-1
• n is an integer.
• Either x is not zero or n > 0.
• -104 <= xn <= 104

일단 첫 인상은 굉장히 만만해 보인다.

 

한 번 Dive deep into it을 해보자.

 

1. C

double myPow(double x, int n) {
    if(n==0) return 1;
    else if(n>0){
        return x*myPow(x,n-1);
    }else{
        return 1/(x*myPow(x,-n-1));
    }
}

이렇게 하니까 overflow가 발생한다;; 

짜증이 나네 지들이 범위를 크게 잡아 놓고 뭐가 문제라고 하는건지!!

 

1.C, 사실 그냥 pow(x,n) 하는게 1등이긴하다. 요지는, recurse 깊이를 줄이기
double myPow(double x, int n) {
    if(n==0) return 1;
    long long N = n;
    if(N<0){
        x = 1 / x ;
        N = -(N);
    }
    double half = myPow(x, N/2);
    if(N%2 == 0){ //even num
        return half*half;
    }else{
        return half*half*x;
    }
}

 

2. C++

class Solution {
public:
    double myPow(double x, int n) {
        if(n==0) return 1;
        long long N = n;
        if(N<0){
            x = 1/x;
            N = (-N);
        }
        double half = myPow(x,N/2);
        if(N%2==0) return half*half;
        else return half*half*x;
    }
};

 

3. Python

Recursion depth에 걸려버림~~

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n==0 : return 1
        elif n>0 : return x*self.myPow(x,n-1)
        else : return 1/(x*self.myPow(x,-n-1))