69. Sqrt(x) Leetcode Solution
Sqrt(x) Leetcode Problem :
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.
Sqrt(x) Leetcode Solution :
Constraints :
- 0 <= x <= 2^31 – 1
Example 1:
- Input: x = 8
- Output: 2
Intuition :
We want to find the square root of a given non-negative integer x. Instead of using a traditional approach like repeatedly subtracting numbers until we reach 0 or using a library function, we’ll use a smarter method called “Binary Search.” Binary Search helps us quickly find the square root by repeatedly narrowing down the search range.
Approach :
We first check if x is 0 or 1. If it is, we know that the square root of 0 and 1 is 0 and 1 respectively, so we directly return x.
For any other value of x, we set up a search range between 1 and x. We initialize two variables start and end to represent the range.
Now comes the clever part: We use a while loop to repeatedly divide the search range in half (Binary Search) to find the square root.
In each iteration of the loop, we calculate the middle value mid using the formula start + (end – start) / 2. This formula ensures that we don’t encounter any integer overflow when dealing with large values of x.
Next, we calculate the square of mid and compare it with x.
If the square of mid is greater than x, we know the square root lies in the lower half of the search range. So, we move the end pointer to the left to narrow down the search range.
If the square of mid is equal to x, we have found the square root! So, we return mid as the answer.
If the square of mid is less than x, we know the square root lies in the upper half of the search range. So, we move the start pointer to the right to continue the search.
We repeat steps 4 to 8 until the start pointer becomes greater than the end pointer. At this point, we have found the floor value of the square root, and end holds that value.
To ensure that we return the correct floor value of the square root, we round down the value of end to the nearest integer using the Math.round() method.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int mySqrt(int x) {
if (x == 0 || x == 1)
return x;
int start = 1;
int end = x;
int mid = -1;
while (start <= end) {
mid = start + (end - start) / 2;
long long square = static_cast< long long>(mid) * mid;
if (square > x)
end = mid - 1;
else if (square == x)
return mid;
else
start = mid + 1;
}
return static_cast< int>(std::round(end));
}
};
class Solution {
public int mySqrt(int x) {
if (x == 0 || x == 1)
return x;
int start = 1;
int end = x;
int mid = -1;
while (start <= end) {
mid = start + (end - start) / 2;
if ((long) mid * mid > (long) x)
end = mid - 1;
else if (mid * mid == x)
return mid;
else
start = mid + 1;
}
return Math.round(end);
}
}
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
first, last = 1, x
while first <= last:
mid = first + (last - first) // 2
if mid == x // mid:
return mid
elif mid > x // mid:
last = mid - 1
else:
first = mid + 1
return last
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
