The whole-number square root
A layout routine sizes a square grid big enough to hold a number of tiles, and needs the square root as a whole number without trusting floating point.
- Return the largest whole number whose square is no greater than the input.
- The input is zero or more.
- Do not lean on a floating-point square root; the answer has to be exact for large tiless.
integer_root(tiles: int) → int
Where you start
def integer_root(tiles: int) -> int:
Worked examples
| Call | Result |
|---|---|
integer_root(16) | 4 |
integer_root(15) | 3 |
integer_root(1) | 1 |
integer_root(0) | 0 |
Hint
The answer lies between 0 and the input. Halve that range each step, testing whether the middle squared is still within bounds.
Reference solution in Python
def integer_root(tiles: int) -> int:
lo, hi, best = 0, tiles, 0
while lo <= hi:
mid = (lo + hi) // 2
if mid * mid <= tiles:
best = mid
lo = mid + 1
else:
hi = mid - 1
return best