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
Java 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
int integerRoot(int tiles) {
}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 Java
int integerRoot(int tiles) {
long lo = 0, hi = tiles, best = 0;
while (lo <= hi) {
long mid = (lo + hi) / 2;
if (mid * mid <= tiles) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return (int) best;
}