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:
Example 2:
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:
Solution 2: Newton's method
Idea:
.
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:
Last updated
Was this helpful?