69. Sqrt(x)
Given a non-negative integer x, compute its integer square root: the largest non-negative integer r such that r * r <= x. Equivalently, take the true square root and round it down to a whole number — for x = 27 the real root is about 5.196, so the answer is 5.
Return that integer r.
Calling a built-in square-root or fractional-power routine defeats the exercise; find r with integer arithmetic.
Example 1:
Input: x = 16
Output: 4
Explanation: 16 is a perfect square: 4 × 4 = 16, so the root is exact.
Example 2:
Input: x = 27
Output: 5
Explanation: 5 × 5 = 25 ≤ 27 but 6 × 6 = 36 > 27, so rounding the real root (≈5.196) down gives 5.
Constraints:
- 0 ≤ x ≤ 2³¹ - 1
Hints:
The squares 0, 1, 4, 9, 16, … grow strictly, so the predicate `r * r <= x` is true for a prefix of candidates and false afterwards. You're hunting the boundary. Note the answer never exceeds about 46341 for the largest allowed x.
A monotonic true…true-false…false predicate is exactly what binary search consumes: keep the last mid whose square fits and move right, otherwise move left. Watch out that `mid * mid` overflows 32-bit arithmetic — square in a 64-bit type.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: x = 16
Expected output: 4