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++ orx ** 0.5in 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
}
Input
Output
#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;
}
}
};
Input
Output
#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;
}
}
Input
Output
#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;
};
Input
Output
#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
Input
Output
#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;
}
}
}
Input
Output