0069. Sqrt(t)¶
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.
Analysis¶
-
we could "try" all the values from 0 to x, and find the largest value y where y * y is less than x. y is our answer — we can use binary search for this problem. Don't forget to subtract 1 after calculation, since the question wants to discard all the digits after the decimal (1.2->1).
-
Newton Iteration: to find x^2=n, we can first rearrange our function into f(x)=n-x^2, and we want to find the solution when f(x)=0. The key point is the average result is calculate by "ans = (ans + x / ans) / 2";
For instance, when calculating sqrt(2) :
Guess Result Quotient Average Result
1 2 / 1 = 2 (2 + 1) / 2 = 1.5
1.5 2 / 1.5 = 1.3333 (1.3333 + 1.5) / 2 = 1.4167
1.4167 2 / 1.4167 = 1.4118 (1.4167 + 1.4118) / 2 = 1.4142
... ...
Code 1¶
class Solution {
public:
int mySqrt(int x) {
if (x <= 1) return x;
// left is our candidate, right is our target
int left = 0, right = x;
while (left < right) {
int mid = left + (right - left) / 2;
if (x / mid >= mid) left = mid + 1;
else right = mid;
}
return right - 1;
}
};
Code 2¶
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
double res = 1, pre = 0;
while (abs(res - pre) > 1e-6) {
pre = res;
res = (res + x / res) / 2;
}
return int(res);
}
};