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.
integerRoot(tiles: int) → int
Go needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
func integerRoot(tiles int) int {
}Worked examples
| Call | Result |
|---|---|
integerRoot(16) | 4 |
integerRoot(15) | 3 |
integerRoot(1) | 1 |
integerRoot(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 Go
func integerRoot(tiles int) int {
lo, hi, best := 0, tiles, 0
for lo <= hi {
mid := (lo + hi) / 2
if mid*mid <= tiles {
best = mid
lo = mid + 1
} else {
hi = mid - 1
}
}
return best
}