[C++] LeetCode : Sqrt(x)

Question

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

 

음이 아닌 정수 x가 주어졌을 때, 제곱근 x를 구하여라.

다만 제곱근 x를 구할 때 소수점 아래수는 버린다. 

 

Note: 내장 함수를 사용하면 안 된다. 

 

제약사항

• 0 <= x <= 2^31 - 1

---

Solution

문제를 풀 때 고려한 사항

• return type은 integer
• 소수점 아래는 truncated 한다. 

---

Solution1 (Linear Search)

class Solution {
public:
    int mySqrt(int x) {
        long i = 0; 
		
		while(1){
			if((i * i <= x) && (x < (i+1) * (i+1))){
				return i;
			}
			i++;
		}
		
		return -1; // not_found
    }
};

주어진 숫자 x가 int형의 범위이기 때문에 46340번 루프를 돈 후 결과가 나온다. 

int형의 범위로 제한 한다면 binary search를 통해서 searching 속도를 높일 수 있을 것 같다.

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

Solution2 (Binary Search)

class Solution {
public:
    int mySqrt(int x) {
		long start = 0;
        long end = 46340; 
		long mid;
		
		while(start<=end){
			mid = (start+end) / 2;
			if((mid * mid <= x) && (x < (mid+1) * (mid+1)) ){
				return mid;
			}else if(mid*mid < x){
				start = mid+1;
			}else{
				end = mid-1;
			}
		}
		
		return -1; // not_found
    }
};

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

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

Explore - LeetCode