69_Sqrt(x)
[Easy] [Math]
Implementint 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 1: Binary Search
Idea:
If mid**2 <= x and (mid+1)**2 > x, then mid is the solution.
If mid**2 > x, then throw away right part.
If mid**2 < x and (mid+1)**2 <= x, then throw away left part.
Time Complexity:
Space Complexity:
def mySqrt(x):
"""
:type x: int
:rtype: int
"""
left, right = 0, x
while left <= right:
mid = left + (right - left)//2
if mid**2 <= x and (mid+1)**2 > x:
return mid
elif mid**2 > x:
right = mid - 1
else:
left = mid + 1
Solution 2: Newton's method
Idea:
Newton's method is a method for finding successively better approximations to the roots (or zeroes) of a real-valued function. In this problem, we want to find the floor of st.
.

To use Newton's method,
pick a initial value as . Why not use 0? because the derivative at 0 is 0, and Newton's method doesn't work.
update as
use floor instead of the real value, until we have the first time. (Why this condition work? because this process ensure the potential approach to the solution monotonicly because is monotone for )
Time Complexity:
Space Complexity:
def mySqrt(x):
"""
:type x: int
:rtype: int
"""
ans = x
while ans**2 > x:
ans = (ans + x/ans) // 2
return ans
Last updated
Was this helpful?