Problem

Link

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

1
2
3
4

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

1
2
3

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Solution

Solution 1 - Using Brute Force

단순 브루트 포스 방법으로 풀 수 있다.

y = √x

⇒

y^2 = x

⇒

y^2 ≤ x

따라서 y 를 0에서 부터 1씩 증가시키면서, 만약 y^2 가 x 보다 크다면 y-1 을 리턴할 수 있다.

1
2
3
4
5
6

class Solution:
    def mySqrt(self, x: int) -> int:
        y = 0
        while y * y <= x:
            y += 1
        return y -1

Solution 2 - Using Binary Search

Space Complexity is O(1)

공간 복잡도를 최소화 하기 위해서 이진 탐색을 사용할 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def mySqrt(self, x: int) -> int:
        if x == 0:
            return 0
        l, r = 1, x 
        while l <= r:
            mid = l + (r - l) // 2
            if mid * mid == x:
                return mid
            elif mid * mid > x:
                r = mid - 1
            else:
                l = mid + 1
        return r

의문점

왜 Mid 값을 구할 때 (left + right) // 2 가 아니라 left + (right - left) //2 를 쓰는 것인가?

⇒

Overflow 때문에 그렇다.

left + right ≥ right 는 성립할 수 있지만, left + (right - left) / 2 ≤ right 으로 우측에 있는 값은 right 을 넘을 수 없기 때문에, Overflow 가 발생할 수 없음. 따라서 해당 수식을 사용한다.

Reference.

• https://stackoverflow.com/questions/27167943/why-leftright-left-2-will-not-overflow
• Chat GPT