Dare2Solve
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
.
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.
Initialization:
x
is 0
by returning 0
immediately.left
to 1
and right
to x
. These represent the search range for the integer square root.Binary Search:
left
is less than or equal to right
.mid
as the average of left
and right
.mid_squared
as mid * mid
.mid_squared
with x
:
mid_squared
is equal to x
, mid
is the exact integer square root, so return mid
.mid_squared
is less than x
, update result
to mid
(since mid
is a candidate for the integer square root) and search the right half by setting left
to mid + 1
.mid_squared
is greater than x
, search the left half by setting right
to mid - 1
.Return the Result:
result
contains the integer part of the square root.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.
O(1)
. The algorithm uses a constant amount of extra space beyond the input size.
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<long long>(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)
}
};
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
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)
}
}
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;
};