The problem
Compute ⌊√x⌋ without using built-in exponent/sqrt functions.
Stuck? Reveal hints one at a time
How to approach it
- 1Binary search k in [1, x] (handle x < 2 directly).
- 2If mid ≤ x / mid, mid is valid — remember it and search higher.
- 3Otherwise search lower. Return the last valid mid.
Key insight
"Largest value passing a test" is the mirror image of lower-bound search — remember the passing candidate as you move lo up.
The solution
Watch out for
- mid * mid overflows 32-bit ints for large x — divide instead of multiply in such languages.
- ⌊√x⌋ for x ≥ 2 is at most x/2, so hi = x/2 halves the range for free.