Square Patio Tiles
You have a pile of identical square paving tiles left over from a job. You want to lay them as one square patio, as large as possible. A patio with side 4 needs 4 × 4 = 16 tiles. Tiles that do not fit go back in the shed.
Given the number of tiles, how long can the side of the patio be?
Your task
Write largestSide(tiles). Return the largest whole number k with k × k ≤ tiles. With 0 tiles the answer is 0.
Do not use a built-in square root or power function. Find k by searching.
largestSide(tiles: int) → int
Examples
tiles = 17
4
A side of 4 uses 16 tiles, and 1 is left over. A side of 5 would need 25, which you do not have. So 4.
tiles = 36
6
6 × 6 = 36 exactly, so every tile is used.
Constraints
- 0 ≤ tiles ≤ 2,000,000,000
Start with brute force
Try side 1, 2, 3, … and stop at the first one whose square is more than tiles. The answer is one less.
That takes about √tiles steps. For 2,000,000,000 tiles that is 44,721 steps. Not terrible, but binary search needs about 31, and the same idea scales to problems where a linear scan is far too slow.
Hints
0 of 4 shown- Hint 1
Write down sides 0, 1, 2, 3, 4, 5, 6 and mark each one "fits" or "too big" for 17 tiles. What pattern do the marks make?
- Hint 2
Every side up to some point fits, and every side after it is too big. The answer is the last side that fits. That is a sorted yes/no row, even though nobody gave you a list.
- Hint 3
Binary search over side lengths from 0 to
tiles. For a middle side, the check is justmid * mid <= tiles. If it fits, the answer ismidor larger. If not, it is smaller. - Hint 4
Keep
lo = 0,hi = tiles. Whilelo < hi, take the upper middle,mid = floor((lo + hi + 1) / 2). If it fits,lo = mid; elsehi = mid - 1. The upper middle stops the loop from getting stuck whenhi = lo + 1.
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
There is no list here, but there is still a sorted row of yes/no answers: "does a side of k fit?" is yes for small k and no for large k. Binary search finds the last yes.
Trace 17 tiles:
lo = 0,hi = 17,mid = 9. 81 > 17, too big.hi = 8.lo = 0,hi = 8,mid = 4. 16 ≤ 17, fits.lo = 4.lo = 4,hi = 8,mid = 6. 36, too big.hi = 5.lo = 4,hi = 5,mid = 5. 25, too big.hi = 4.lo = hi = 4. Return 4.
Look at step 4. With the usual lower middle, mid would be 4, it would fit, lo would stay 4, and the loop would never end. When the "yes" branch sets lo = mid, round the middle up.
In languages with 32-bit integers, mid * mid can overflow for large mid. There, compare mid <= tiles / mid instead. JavaScript and Python numbers are big enough for this range.
function largestSide(tiles) {
let lo = 0, hi = tiles; // the answer is in [lo, hi]
while (lo < hi) {
const mid = Math.floor((lo + hi + 1) / 2); // upper middle
if (mid * mid <= tiles) lo = mid; // mid fits: answer is mid or bigger
else hi = mid - 1; // too big: answer is smaller
}
return lo;
}def largest_side(tiles):
lo, hi = 0, tiles # the answer is in [lo, hi]
while lo < hi:
mid = (lo + hi + 1) // 2 # upper middle
if mid * mid <= tiles:
lo = mid # mid fits: answer is mid or bigger
else:
hi = mid - 1 # too big: answer is smaller
return loRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.