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:
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:
Last updated