## Algorithm

Problem Name: 69. Sqrt(x)

Given a non-negative integer `x`, return the square root of `x` rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use `pow(x, 0.5)` in c++ or `x ** 0.5` in python.

Example 1:

```Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.
```

Example 2:

```Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.
```

Constraints:

• `0 <= x <= 231 - 1`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int mySqrt(int x) {
#if 1
int left, right, mid, k;
if (!x) return 0;
left = 1;
right = (x  <  46340 * 2) ? (x + 1) / 2 : 46340;
while (left <= right) {
mid = left + (right - left) / 2;
//printf("mid: %d\n", mid);
k = mid * mid;
if (k == x) return mid;
if (k  <  x) left = mid + 1;
else     right = mid - 1;
}
return right;
#else
unsigned long long r = (x + 1) / 2;
if (r > 46340) r = 46340;
while (r * r > x) {
//printf("r: %lld\n", r);
r = (r + x / r) / 2;
}
​
return r;
#endif
}
``````
Copy The Code &

Input

cmd
x = 4

Output

cmd
2

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
int mySqrt(int x) {
if(x == 0) return x;
int lo = 1, hi = x;
while (true) {
int mid = lo + (hi - lo)/2;
if (mid > x/mid) hi = mid - 1;
else if (mid + 1 > x/(mid + 1)) return mid;
else lo = mid + 1;
}
}
};
``````
Copy The Code &

Input

cmd
x = 8

Output

cmd
2

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int mySqrt(int x) {
if (x < 2) {
return x;
}
int left = 2;
int right = x / 2;
while (left  < = right) {
int mid = (left + right) / 2;
long square = ((long) mid) * mid;
if (square > x) {
right = mid - 1;
} else if (square  <  x) {
left = mid + 1;
} else {
return mid;
}
}
return right;
}
}
``````
Copy The Code &

Input

cmd
x = 4

Output

cmd
2

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const mySqrt = function(x) {
let left = 0, right = x;
while (left  <  right) {
let mid = right - ((right - left) >> 1);
if (mid * mid > x) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
};
``````
Copy The Code &

Input

cmd
x = 4

Output

cmd
2

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def mySqrt(self, x: int) -> int:
l, r = 0, x
while l <= r:
mid = (l + r) // 2
if mid * mid <= x:
l = mid + 1
else:
r = mid - 1
return l - 1
``````
Copy The Code &

Input

cmd
x = 4

Output

cmd
2

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _069_Sqrt
{
public int MySqrt(int x)
{
if (x < 1) { return x; }

double last = 0.0, result = 1.0;
while (last != result)
{
last = result;
result = (result + x / result) / 2;
}

return (int)last;
}
}
}
``````
Copy The Code &

Input

cmd
x = 4

Output

cmd
2