Given a non-negative integer `n`, compute and return the integer square root of `n`. The integer square root is the largest integer `x` such that `x*x <= n`.
Input: 4
Output: 2
Input: 8
Output: 2
Input: 6096
Output: 78
The integer square root is the largest integer x where x*x <= n. Since x*x grows monotonically, we can use binary search over [0, n] to efficiently locate x.
low = 0, high = n, and ans = 0.low <= high:
mid = low + (high - low) / 2 to avoid overflow.square = mid * mid. (Cast mid to long in C++/Java to prevent overflow.)square <= n, set ans = mid and search right (low = mid + 1).high = mid - 1).ans.class Solution {
public:
int mySqrt(int n) {
int low = 0, high = n, ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
long square = (long) mid * mid;
if (square <= n) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
};class Solution {
public int mySqrt(int n) {
int low = 0, high = n, ans = 0;
while (low <= high) {
int mid = low + (high - low) / 2;
long square = (long) mid * mid;
if (square <= n) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
}def mySqrt(n: int) -> int:
low, high, ans = 0, n, 0
while low <= high:
mid = low + (high - low) // 2
if mid * mid <= n:
ans = mid
low = mid + 1
else:
high = mid - 1
return ansfunction mySqrt(n) {
let low = 0, high = n, ans = 0;
while (low <= high) {
let mid = Math.floor(low + (high - low) / 2);
if (mid * mid <= n) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}Time Complexity: O(log n) due to binary search halving the range each iteration.
Space Complexity: O(1) as only a few integer variables are used.
Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.