Problem
Implement int sqrt(int x).
Compute and return the square root of x.
My Solution
class Solution {
public int mySqrt(int x) {
if (x == 0) {
return 0;
}
for (int i = 1; i <= x / 2 + 1; i++) {
if (x / i == i) {
return i;
} else if (x / i < i) {
return i - 1;
}
}
return x;
}
}
Great Solution
public int mySqrt(int x) {
if (x == 0) return 0;
long i = x;
while(i > x / i)
i = (i + x / i) / 2;
return (int)i;
}
