Sqrt(x)
EasyProblem 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.
Example 1:
Input: x = 4
Output: 2
Explanation: The square root of 4 is 2.
Example 2:
Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., rounded down is 2.
Intuition
We need to find the largest integer k such that k² ≤ x.
Since the square root of x must be between 0 and x, we can use binary search to efficiently find the answer. For each mid value, we check if mid² is less than, equal to, or greater than x.
Key insight: The answer lies in a sorted range [0, x], making binary search perfect for this problem.
Visual Walkthrough
Let's find the square root of x = 8
Step 1: Initialize search range
mid = (0 + 8) / 2 = 4
Step 2: Check mid² = 16 > 8
16 > 8, so the answer is in the left half
mid = (0 + 3) / 2 = 1
Step 3: Check mid² = 1 < 8
1 < 8, so update result and search right half
result = 1 (potential answer)
Step 4: Check mid² = 6.25 < 8
mid = 2, 2² = 4 < 8, update result and search right
result = 2 (updated)
Final: Check 3² = 9 > 8
3² = 9 > 8, search ends. Return result = 2
sqrt(8) = 2
Solution
class Solution:
def mySqrt(self, x: int) -> int:
# Handle edge cases
if x == 0:
return 0
# Binary search in range [1, x]
left, right = 1, x
result = 0
while left <= right:
mid = left + (right - left) // 2
# Check if mid is a valid square root
if mid * mid == x:
return mid
elif mid * mid < x:
result = mid # Store potential answer
left = mid + 1 # Search right half
else:
right = mid - 1 # Search left half
return resultclass Solution {
public int mySqrt(int x) {
// Handle edge case
if (x == 0) {
return 0;
}
// Binary search in range [1, x]
int left = 1, right = x;
int result = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
// Use division to avoid overflow
if (mid <= x / mid) {
result = mid; // Store potential answer
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return result;
}
}class Solution {
public:
int mySqrt(int x) {
// Handle edge case
if (x == 0) {
return 0;
}
// Binary search in range [1, x]
int left = 1, right = x;
int result = 0;
while (left <= right) {
long long mid = left + (right - left) / 2;
if (mid * mid == x) {
return mid;
} else if (mid * mid < x) {
result = mid; // Store potential answer
left = mid + 1; // Search right half
} else {
right = mid - 1; // Search left half
}
}
return result;
}
};Important: Overflow Prevention
Watch out for overflow! When computing mid * mid, the product can exceed the maximum integer value for large inputs.
Solutions:
- Use
long long(C++) orlong(Java) for mid - Rearrange the comparison: instead of
mid * mid > x, usemid > x / mid
Complexity Analysis
Time Complexity: O(log n)
Binary search halves the search space with each iteration. For input x, we need at most log₂(x) iterations to find the answer.
Space Complexity: O(1)
We only use a constant amount of extra space for variables (left, right, mid, result), regardless of input size.
Alternative: Newton's Method
Newton's method converges much faster than binary search. Starting with an initial guess, we iteratively improve it using:
def mySqrt(self, x):
if x == 0:
return 0
r = x
while r * r > x:
r = (r + x // r) // 2
return r
This method converges in O(log log n) iterations, making it even faster than binary search for very large numbers.