Problems › TypeScript › patterns
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
Where you start
function integerRoot(tiles: number): number {
}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 TypeScript
function integerRoot(tiles: number): number {
let lo = 0;
let hi = tiles;
let best = 0;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (mid * mid <= tiles) {
best = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return best;
}