Sqrt(x)
Asked at Google
Problem
Implement the sqrt(x) function that computes and returns the square root of a non-negative integer x. The return type is integer, so you must return the integer part of the square root. For example, sqrt(8) returns 2, not 2.828.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → |
How to Think About It
Brute force: iterate from 1 to x and check if i*i equals x.
If i*i > x, then i-1 is the answer. This is O(sqrt(x)) time.
Binary search on the range [1, x/2+1] to find the largest integer whose square is <= x.
For each mid, compare mid*mid with x to decide whether to go left or right.
Optimal: use binary search in O(log x) time and O(1) space.
Optimal Approach
Use binary search on the range [0, x]. For each mid, compute midmid. If midmid == x, return mid. If midmid > x, search left; otherwise search right. The answer is the last mid where midmid <= x. This runs in O(log x) time and O(1) space.
What Trips People Up in Real Interviews
Edge cases: x = 0 returns 0, x = 1 returns 1.
Watch for integer overflow: use long long for mid*mid comparison.
The answer is the largest integer r such that r*r <= x.
Newton's method is an alternative that converges faster in practice.
Clarify with interviewer whether x is always non-negative.
Solution Code
class Solution:
def mySqrt(self, x: int) -> int:
if x < 2:
return x
lo, hi = 1, x // 2
while lo <= hi:
mid = (lo + hi) // 2
sq = mid * mid
if sq == x:
return mid
elif sq < x:
lo = mid + 1
else:
hi = mid - 1
return hiFrequently Asked Questions
What is the Sqrt(x) problem?
Implement the sqrt(x) function that computes and returns the square root of a non-negative integer x. The return type is integer, so you must return the integer part of the square root. For example, sqrt(8) returns 2, not 2.828.
How do you solve Sqrt(x)?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Sqrt(x)?
Sqrt(x) is asked at Google. It is a easy difficulty problem.
What are common mistakes on Sqrt(x)?
- Edge cases: x = 0 returns 0, x = 1 returns 1.
- Watch for integer overflow: use long long for mid*mid comparison.
- The answer is the largest integer r such that r*r <= x.
- Newton's method is an alternative that converges faster in practice.
- Clarify with interviewer whether x is always non-negative.