Compute the integer square root of a non-negative integer without using floating-point precision tricks.
Sqrt(x)
Given a non-negative integer x, return the greatest integer r such that r*r <= x.
In other words, compute the floor of the square root of x.
You should avoid using built-in square root functions that rely on floating-point precision. The goal is to determine the answer using integer reasoning and an efficient search strategy.
Input Format
- A single integer
x. xis guaranteed to be non-negative.
Output Format
- Return an integer
rsuch thatr*r <= x < (r+1)*(r+1).
Constraints
0 <= x- The answer must fit in a 32-bit signed integer for the usual interview version of this problem.
- Use integer arithmetic where possible to avoid precision issues.
Example 1
Input
x = 4
Output
2
Explanation
Since 2² = 4, the floor square root is 2.
Example 2
Input
x = 8
Output
2
Explanation
2² = 4 <= 8 and 3² = 9 > 8, so the answer is 2.
Show 1 more example
Example 3
Input
x = 0
Output
0
Explanation
The square root of 0 is 0.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.