Sqrtx
Created: November 8, 2018 by [lek-tin]
Last updated: March 25, 2020
Implement int sqrt(int x).
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.
Example 1
Input: 4
Output: 2
Example 2
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842…, and since the decimal part is truncated, 2 is returned.
Solution
# log(x)
class Solution:
def mySqrt(self, x: int) -> int:
left, right = 1, x
while left <= right:
mid = left + (right-left)//2
if mid > x/mid:
right = mid - 1
else:
left = mid + 1
# left == right or left > right
# since we need to floor the result, we return right
return right