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.
My code:
class Solution:
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x==0:
return 0
result=self.Sqrt(x,0,x)
return int(result)
def Sqrt(self,x,i,j):
if j-i<=2:
check_index=i
for k in range(i,j+1):
if k**2<=x:
check_index=k
assert (check_index+1)**2>x
return check_index
mid=int((i+j)/2)
if mid**2>x:
return self.Sqrt(x,i,mid)
else:
return self.Sqrt(x,mid,j)
Solution: https://leetcode.com/problems/sqrtx/