[Leetcode] 69. Sqrt(x)

題目 : 69. Sqrt(x)

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.

1.

x = 8

依照題目所說的取最接近小於等於該開根號後所得出的整數部分，所以答案是i

class Solution:
    def mySqrt(self, x: int) -> int:
        
        # 先將例外的例子，如0和1先行做判斷
        # 0和1的根號分別都是0和1，所以可以直接回傳本身的數字
        if x == 0 or x == 1:
            return x
        
        # 思路如上圖所示
        for i in range(x):
            if i*i <= x and x < (i+1)*(i+1) :
                return i