Binary search version:

```
class Solution {
public:
int mySqrt(int x) {
int l = 0, r = x;
while(l < r){
long long mid = l + 1 + (r - l)/2;
if(mid * mid < x) l = mid;
else if(mid * mid == x) return mid;
else r = mid - 1;
}
return l;
}
};
```

Newton Iteration:

```
class Solution {
public:
int mySqrt(int x) {
long res = x;
while(res * res > x) res = (res + x / res)/2;
return res;
}
};
```