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.
public class Solution {
public int MySqrt(int x) {
long num = x;
while (num*num > x)
num = (num + x/num) / 2;
return (int) num;
}
}Time Complexity: O(logn)
Space Complexity: O(1)
Given y = f(x), find the root x such that f(x) = 0, geometrically speaking, find the intersection of the function y and the x-axis.
For a roughly estimated root x0, it's coordinate on the function is P(x0, f(x0)). We can find P's tangent line L whose slope is m, such that the intersection of the L and the x-axis, say S(x1, 0), it's function value f(x1) is closer to the real root of y = f(x), comparing to the f(x0).
Set m = f'(x0), where f' denotes the differential on x0 ... (1) The slope m is defined by PS: m = (f(x0) - 0) / (x0 - x1) ... (2) Combine (1) (2), f'(x0) = f(x0) / (x0 - x1) => x0 - x1 = f(x0) / f'(x0) => x1 = x0 - f(x0) / f'(x0)
x(n+1) = x(n) - f(x(n)) / f'(x(n)) By applying Newton's method to the root problem, finding the r such that r^2 equals to the input x is the same as finding the root of f(r) where
f(r) = r^2 - x = 0 => r(n+1) = r(n) - f(r(n)) / f'(r(n)) => r(n+1) = r(n) - (r(n)^2 - x) / 2 * r(n) => r(n+1) = r(n) - r(n) / 2 + x / 2 * r(n) => r(n+1) = (r(n) + x / r(n)) / 2
