[69] Sqrt(x)
https://leetcode.com/problems/sqrtx/description/
- algorithms
- Easy (29.86%)
- Source Code: 69.sqrtx.py
- Total Accepted: 351.7K
- Total Submissions: 1.1M
- Testcase Example: '4'
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.
python
class Solution(object):
def mySqrt(self, x):
"""
:type x: int
:rtype: int
"""
if x == 0: return 0
l, r = 1, x
while l <= r:
mid = (l+r)/2
multify = mid * mid
if multify == x: return mid
elif multify < x:
if (mid+1)*(mid+1)>x:
return mid
l = mid
else:
r = mid
return 1
#
#
# s = Solution()
# print s.mySqrt(4)
# print s.mySqrt(10)
# print s.mySqrt(9)