In this guide, you will get 69. Sqrt(x)LeetCode Solution with the best time and space complexity. The solution to Sqrt(x) problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(\log x)
Space Complexity: O(1)
69. Sqrt(x)LeetCode Solution in C++
class Solution {
public:
int mySqrt(int x) {
unsigned l = 1;
unsigned r = x + 1u;
while (l < r) {
const unsigned m = (l + r) / 2;
if (m > x / m)
r = m;
else
l = m + 1;
}
// l := the minimum number s.t. l * l > x
return l - 1;
}
}; /* code provided by PROGIEZ */
69. Sqrt(x)LeetCode Solution in Java
class Solution {
public int mySqrt(long x) {
long l = 1;
long r = x + 1;
while (l < r) {
final long m = (l + r) / 2;
if (m > x / m)
r = m;
else
l = m + 1;
}
// l := the minimum number s.t. l * l > x
return (int) l - 1;
}
} // code provided by PROGIEZ
69. Sqrt(x)LeetCode Solution in Python
class Solution:
def mySqrt(self, x: int) -> int:
return bisect.bisect_right(range(x + 1), x,
key=lambda m: m * m) - 1 # code by PROGIEZ
