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.

Difficulty: introductory

Starter code:

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

Solutions:
class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         return int(x**0.5)

class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         if x<=1:
             return x
         low = 0
         high = x
 
         while low < high:
             mid = (high+low)/2
             if abs(mid**2-x) < 1e-6:
                 return int(mid)
             elif mid**2 > x:       
                 high = mid
             else:
                 low = mid

class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         return int(x**(1/2))

class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         a = x**0.5
 
         return math.floor(a)

class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         return int((x ** (1/2)))

class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         return int((x ** (1/2)))

class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         if x==1 or x==0:
             return x
         left,right=1,x
         while 1:
             mid=left+(right-left)//2
             if mid>x//mid:
                 right=mid-1
             else:
                 if mid+1>x//(mid+1):
                     return mid
                 left=mid+1
        
         return int(n)


class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         if x==1 or x==0:
             return x
         left,right=1,x
         while 1:
             mid=left+(right-left)//2
             if mid>x//mid:
                 right=mid-1
             else:
                 if mid+1>x//(mid+1):
                     return mid
                 left=mid+1
        
         return int(n)


class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         if x==1 or x==0:
             return x
         left,right=0,x
         mid=(right+left)/2
         while abs(mid*mid-x)>0.01:
             if mid>x/mid:
                 right=mid
             else:
                 left=mid
             mid=(right+left)/2
        
         return int(mid)


class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         if x==1 or x==0:
             return x
         left,right=0,x
         mid=(right+left)/2
         while abs(mid*mid-x)>0.01:
             if mid>x/mid:
                 right=mid
             else:
                 left=mid
             mid=(right+left)/2
        
         return int(mid)


class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         hi = x // 2
         lo = 0
         if x == 1:
             return 1
         while True:
             if hi == lo:
                 return hi
             if hi - lo == 1:
                 if hi * hi > x:
                     return lo
                 return hi
             test = (hi + lo) // 2
             sq = test * test
             if sq == x:
                 return test
             if sq > x:
                 hi = test - 1
             else:
                 lo = test
             


class Solution:
     def mySqrt(self, x):
         """
         :type x: int
         :rtype: int
         """
         if x<=1:
             return x
         up=x
         down=0
         while True:
             n=(up+down)//2
             if n**2==x:
                 return n
             elif n**2<x:
                 if (n+1)**2>x:
                     return n
                 else:
                     down=n
             else:
                 if (n-1)**2<x:
                     return n-1
                 else:
                     up=n