[C++] LeetCode : Pow(x, n)

Question

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

x의 n승을 리턴하는 pow 함수를 구현하라.

 

제약사항

• -100.0 < x < 100.0
• -2^31 <= n <= 2^31-1
• -10^4 <= xn <= 10^4

---

Solution

문제를 해결할 때 고려한 사항

• 주어진 x 의 범위가 실수 자료형이다.
• n의 범위가 int형 범위의 최소부터 최대까지 나올 수 있다.
• 다만 xⁿ의 결과가 -10^4 부터 10^4으로 범위 안이다. 

---

Solution1 

단순하게 생각해보면 pow 함수는 x를 n번 곱하는 동작이기 때문에 이를 그대로 구현할 수 있다. 

class Solution {
public:
    double myPow(double x, int n) {
		double ans = 1;

        if(n>=0){
    		while(n--) ans *= x;        
        }else{
            while(n++) ans *= 1/x;
        }
		return ans;
    }
};

이때의 시간복잡도는 O(n)이다. 
하지만 잘 생각해보면 연산의 횟수를 줄일 수 있다. 예를 들어, 2x2x2x2 = 2⁴ = 2²x 2² 계산량이 절 반으로 줄어들어 O(n) 보다 적은 시간으로 계산을 수행할 수 있다. 

• Time complexity : O(n) 
• Space Complexity : O(1) 

Solution2

class Solution {
public:
	double myPow(double x, int n) {
		double ans = 1.0;
		long copy_n = n;

		if (copy_n < 0) {
			copy_n = -1 * copy_n;
		}

		while (copy_n > 0) {
			if (copy_n & 1) {
				ans = ans * x;
				copy_n = copy_n - 1;
			}
			else {
				x = x * x;
				copy_n >>= 1;
			}
		}

		if (n < 0) {
			ans = (double)(1.0) / (double)(ans);
		}

		return ans;
	}
};

// 해당 문제의 Discuss 참고

 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/113/math/818/

Explore - LeetCode