Description:
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++ orx ** 0.5in python.
Examples:
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.Solution in Python:
Python
class Solution:
def mySqrt(self, x: int) -> int:
# Special case for x = 0 or x = 1
if x < 2:
return x
# Initialize the left and right pointers for binary search
left, right = 0, x
while left <= right:
# Calculate the mid-point to avoid overflow
mid = left + (right - left) // 2
mid_squared = mid * mid
if mid_squared == x:
# If mid*mid is exactly x, mid is the square root
return mid
elif mid_squared < x:
# If mid*mid is less than x, discard the left half
left = mid + 1
else:
# If mid*mid is greater than x, discard the right half
right = mid - 1
# The right pointer will be at the largest integer whose square is <= x
return rightExplanation:
- Special Case Handling:
- If
xis 0 or 1, returnximmediately as the square root of 0 is 0 and the square root of 1 is 1.
- If
- Binary Search Initialization:
- Initialize
leftto 0 andrighttox.
- Initialize
- Binary Search Loop:
- Continue the loop as long as
leftis less than or equal toright. - Calculate the middle point
midto avoid overflow:mid = left + (right - left) // 2. - Calculate the square of
mid:mid_squared = mid * mid.
- Continue the loop as long as
- Comparison and Adjustment:
- If
mid_squaredis exactlyx, thenmidis the square root, so returnmid. - If
mid_squaredis less thanx, move theleftpointer tomid + 1to search in the right half. - If
mid_squaredis greater thanx, move therightpointer tomid - 1to search in the left half.
- If
- Return Result:
- When the loop terminates,
rightwill be positioned at the largest integer whose square is less than or equal tox, which is the correct answer.
- When the loop terminates,
This approach ensures that the function runs efficiently in logarithmic time, making it suitable even for large values of x within the constraints.
Solution in Javascript:
JavaScript
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
// Special case for x = 0 or x = 1
if (x < 2) {
return x;
}
// Initialize the left and right pointers for binary search
let left = 0;
let right = x;
while (left <= right) {
// Calculate the mid-point to avoid overflow
let mid = Math.floor(left + (right - left) / 2);
let midSquared = mid * mid;
if (midSquared === x) {
// If mid*mid is exactly x, mid is the square root
return mid;
} else if (midSquared < x) {
// If mid*mid is less than x, discard the left half
left = mid + 1;
} else {
// If mid*mid is greater than x, discard the right half
right = mid - 1;
}
}
// The right pointer will be at the largest integer whose square is <= x
return right;
};Solution in Java:
Java
class Solution {
public int mySqrt(int x) {
// Special case for x = 0 or x = 1
if (x < 2) {
return x;
}
// Initialize the left and right pointers for binary search
int left = 0;
int right = x;
while (left <= right) {
// Calculate the mid-point to avoid overflow
int mid = left + (right - left) / 2;
// Calculate mid squared
long midSquared = (long) mid * mid; // Use long to prevent overflow
if (midSquared == x) {
// If mid*mid is exactly x, mid is the square root
return mid;
} else if (midSquared < x) {
// If mid*mid is less than x, discard the left half
left = mid + 1;
} else {
// If mid*mid is greater than x, discard the right half
right = mid - 1;
}
}
// The right pointer will be at the largest integer whose square is <= x
return right;
}
}Solution in C#:
C#
public class Solution {
public int MySqrt(int x) {
// Special case for x = 0 or x = 1
if (x < 2) {
return x;
}
// Initialize the left and right pointers for binary search
int left = 0;
int right = x;
while (left <= right) {
// Calculate the mid-point to avoid overflow
int mid = left + (right - left) / 2;
// Calculate mid squared
long midSquared = (long)mid * mid; // Use long to prevent overflow
if (midSquared == x) {
// If mid*mid is exactly x, mid is the square root
return mid;
} else if (midSquared < x) {
// If mid*mid is less than x, discard the left half
left = mid + 1;
} else {
// If mid*mid is greater than x, discard the right half
right = mid - 1;
}
}
// The right pointer will be at the largest integer whose square is <= x
return right;
}
}