69. Sqrt(x)

Description

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:

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

Example 2:

• 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.

Constraints:

• 0 <= x <= 2³¹ - 1

💡 Hint 1:
Try exploring all integers. (Credits: @annujoshi)

💡 Hint 2:
Use the sorted property of integers to reduced the search space. (Credits: @annujoshi)

Submitted Code

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        left_p = 0        # 왼쪽 포인터 시작 숫자 = 0
        right_p = x       # 오른쪽 포인터 시작 숫자 = x

        while left_p <= right_p:              
            mid = (left_p + right_p) // 2     # 왼쪽과 오른쪽의 가운데 숫자

            if mid * mid == x:
                return mid
            elif mid * mid > x:
                right_p = mid - 1
            else:
                left_p = mid + 1

        return right_p

Runtime: 9 ms | Beats 21.82%
Memory: 12.48 MB | Beats 28.58%

이진 탐색 알고리즘을 사용해서 풀어 보았다.

class Solution(object):
    def mySqrt(self, x):
        n = 0
        while n * n <= x:
            n += 1
        return n - 1

Brute Force 알고리즘으로, 매우 간단하지만 효율이 아주 낮았다.

Other Solutions

1st

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

time complexity: 𝑂(log𝑥)
space complexity: 𝑂(1)

내가 제출한 코드와 거의 같지만 차이점은 x가 0인 경우를 먼저 거르고 왼쪽 포인트를 1부터 시작하는 것이다.

같은 원리지만 이 코드의 런타임이 거의 절반 정도 더 빨랐다.

2nd

class Solution:
    def mySqrt(self, x: int) -> int:
        return int(sqrt(x))

파이썬의 math 모듈에서 제공하는 math.sqrt() 함수를 사용할 경우 간단하게 작성 가능하고 0ms 내에 해결 가능했다.
리트 코드에 math 모듈이 자동 내장되어 있다는 것을 처음 알았다.

3rd

class Solution:
    def mySqrt(self, x: int) -> int:
        ans = x                         # x에서 시작
        while ans*ans > x:              # ans*ans가 x보다 작거나 같아지기 전까지 갱신식 반복
            ans = (ans + x//ans)//2
        return ans 

Newton-Raphson(뉴턴-랩슨) 방법을 사용한 예시로, 갱신식을 반복적으로 적용할수록 루트 x에 더 가까워지는 알고리즘이다. 요구하는 반환값이 int이기 때문에 갱신식의 / 연산자가 // 연산자로 대체됐다.

💡 Update Equation = answer = { answer + (x ÷ answer) } ÷ 2

ans = x = 8

8 = {8 + (8 // 8)} // 2 = (8 + 1) // 2 = 9 // 2 = 4   ← 4 * 4 = 16 
4 = {4 + (8 // 4)} // 2 = (4 + 2) // 2 = 6 // 2 = 3   ← 3 * 3 = 9
3 = {3 + (8 // 3)} // 2 = (3 + 2) // 2 = 5 // 2 = 2   ← 2 * 2 = 4
                                                        (loop over)

∴ ans= 2