Description
Implement int sqrt(int x).
Compute and return the square root of x.
x is guaranteed to be a non-negative integer.
Example
Input: 4, Output: 2
Input: 8, Output: 2
Idea
Use Newton's iteration.
Let f(x) = x^2 - n. To solve for f(x) = 0. Start from some initial x_0, and update as x_{i + 1} = x_i - f(x_i)/f'(x_i) = x_i - (x_i^2 - n)/(2x_i) = (x_i + n/x_i)/2.
Solution
class Solution {
public:
int mySqrt(int x) {
if (!x) return 0;
long rtn = x;
while (rtn * rtn > x) {
if ((rtn - 1) * (rtn - 1) <= x) return (int) rtn - 1;
rtn = (rtn + x / rtn) / 2;
}
return (int) rtn;
}
};
1017 / 1017 test cases passed.
Runtime: 15 ms
