🎨Now live: Try our Free AI Image Generation Feature

Description
The task is to find the integer square root of a non-negative integer x
. The integer square root of x
is the largest integer r
such that r^2
is less than or equal to x
.
Intuition
The problem can be solved efficiently using binary search. Since the square root function is monotonically increasing, we can use binary search to find the integer part of the square root.
Approach
- Initialization:
- Handle the special case where
x
is0
by returning0
immediately. - Initializeleft
to1
andright
tox
. These represent the search range for the integer square root. - Binary Search:
- Perform binary search while
left
is less than or equal toright
. - Calculatemid
as the average ofleft
andright
. - Computemid_squared
asmid * mid
. - Comparemid_squared
withx
: - Ifmid_squared
is equal tox
,mid
is the exact integer square root, so returnmid
. - Ifmid_squared
is less thanx
, updateresult
tomid
(sincemid
is a candidate for the integer square root) and search the right half by settingleft
tomid + 1
. - Ifmid_squared
is greater thanx
, search the left half by settingright
tomid - 1
. - Return the Result:
- After the loop,
result
contains the integer part of the square root.
Complexity
Time Complexity:
O(log x)
, where x
is the input number. The binary search algorithm halves the search space in each iteration, leading to a logarithmic time complexity.
Space Complexity:
O(1)
. The algorithm uses a constant amount of extra space beyond the input size.
Code
C++
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0; // Edge case for zero
int beg = 1, end = x, ans = 0; // Start with 1 because sqrt(0) is 0
while (beg <= end) {
int mid = beg + (end - beg) / 2;
long long midSquared = static_cast(mid) * mid; // Avoid overflow
if (midSquared == x) {
return mid;
} else if (midSquared < x) {
ans = mid; // Record the last valid mid
beg = mid + 1;
} else {
end = mid - 1;
}
}
return ans; // Return the integer part of sqrt(x)
}
};
Python
class Solution:
def mySqrt(self, x: int) -> int:
if x == 0:
return 0
left, right = 1, x
result = 0
while left <= right:
mid = (left + right) // 2
mid_squared = mid * mid
if mid_squared == x:
return mid
elif mid_squared < x:
result = mid
left = mid + 1
else:
right = mid - 1
return result
Java
class Solution {
public int mySqrt(int x) {
if (x == 0) return 0; // Edge case for zero
long left = 1, right = x, result = 0; // Use long to prevent overflow
while (left <= right) {
long mid = left + (right - left) / 2;
long midSquared = mid * mid;
if (midSquared == x) {
return (int) mid;
} else if (midSquared < x) {
result = mid; // Record the last valid mid
left = mid + 1;
} else {
right = mid - 1;
}
}
return (int) result; // Return the integer part of sqrt(x)
}
}
JavaScript
var mySqrt = function(x) {
var beg = 0, end = x, ans = 0;
while(beg <= end) {
var mid = Math.floor((beg + end)/2);
if(mid*mid > x) {
end = mid - 1;
}
else { // mid*mid <= x
ans = mid;
beg = mid + 1;
}
}
return ans;
};