69. Sqrt(x)
Model: qwen2.5-coder:14b
Topics: Math,Binary Search
FAANG asked: 1
Acceptance rate: 35.4%
Problem Breakdown
The problem requires computing the integer part of the square root of a non-negative integer x. The input is a single integer x where 0 <= x <= 231 - 1. The output should be an integer representing the floor value of the square root of x.
Inputs:
- A non-negative integer
x
Outputs:
- An integer that is the floor value of the square root of
x
Implicit Constraints/Edge Cases:
- If
xis 0, the output should be 0. - If
xis 1, the output should be 1. - For large values of
x, the computation must handle integer overflow carefully.
Intuition
A brute-force approach would involve iterating from 0 to x and checking if the square of the current number equals x. However, this approach has a time complexity of O(x), which is inefficient for large values of x.
A better approach involves using binary search. The key insight is that the square root function is monotonically increasing, meaning that as x increases, its square root also increases. This property allows us to efficiently narrow down the possible range of the square root using binary search.
Approach
- Initialize Pointers: Set two pointers,
leftto 0 andrighttox. - Binary Search Loop:
- Calculate the middle point
midas(left + right) // 2. - If
mid * midis equal tox, returnmid. - If
mid * midis less thanx, move theleftpointer tomid + 1. - If
mid * midis greater thanx, move therightpointer tomid - 1.
- Calculate the middle point
- Return Result: After exiting the loop, return
rightas the floor value of the square root.
This approach leverages binary search to achieve a time complexity of O(log x).
Complexity Analysis
- Time Complexity: O(log x) because we are effectively halving the search space in each iteration.
- Space Complexity: O(1) since we are using only a constant amount of extra space for variables.
Solution
def mySqrt(x: int) -> int:
if x == 0 or x == 1:
return x
left, right = 0, x
while left <= right:
mid = (left + right) // 2
if mid * mid == x:
return mid
elif mid * mid < x:
left = mid + 1
else:
right = mid - 1
return right
Edge Cases Handled
- x = 0: The function returns 0 immediately.
- x = 1: The function returns 1 immediately.
- Large values of x: The binary search ensures that the computation remains efficient even for large inputs, as it reduces the number of iterations significantly compared to a linear approach.