Floor of a Square Root
EasyBinary SearchFree
Problem
Given a non-negative integer x, return the largest integer r such that r * r ≤ x.
Do not use a built-in square root, power or exponent function: compute it yourself.
Example 1
- Input:
- x = 17
- Output:
- 4
4 * 4 = 16 ≤ 17 but 5 * 5 = 25 > 17.
Example 2
- Input:
- x = 49
- Output:
- 7
Constraints
- 0 ≤ x ≤ 2^31 - 1
Hint
Show the first hint
The answer is an integer between 0 and x. Which property of a candidate r can you test cheaply?
Walkthrough
How to approach it
01Clarify before coding
- Round down or to the nearest? Down: the largest r with r² ≤ x.
- Can x be 0 or 1? Yes; both are their own square roots.
- Is overflow a concern? r² can reach about 4.6 · 10^18 if you search up to x; keep hi small or use 64-bit math.
02Brute force
Try r = 0, 1, 2, ... while (r + 1)² ≤ x.
Cost: O(√x) time: about 46,000 steps at the top of the range. Acceptable once, but it does not scale and misses the point of the exercise.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.