Tiling a Rectangle with the Fewest Squares
Real-world version: Fewest Square PatchesThe statement here is our own: the same inputs, outputs and technique.
A glazier has to cover a rectangular panel that measures width units across and height units up, using square patches of glass.
Every patch has an integer side length of at least one unit and is laid with its sides parallel to the panel's sides. Patches may be of different sizes, they may not overlap each other, and no patch may stick out past the panel's edge. Together the patches must cover every point of the panel.
Return the smallest number of patches that covers the panel.
Examples
Example 1
- Input
- width = 4, height = 7
- Output
- 5
Five patches cover the panel: a 4 by 4 patch filling the bottom four rows, then a 3 by 3 patch in the left three columns of the remaining band, and three 1 by 1 patches stacked in the last column of that band.
Example 2
- Input
- width = 2, height = 5
- Output
- 4
Four patches cover the panel: two 2 by 2 patches filling the bottom four rows, then two 1 by 1 patches side by side in the top row.
Example 3
- Input
- width = 13, height = 13
- Output
- 1
The panel is already square, so one 13 by 13 patch covers it.
Constraints
- 1 <= width <= 13
- 1 <= height <= 13
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def fewest_square_patches(width: int, height: int) -> int:public int fewestSquarePatches(int width, int height)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 18 test cases: 18 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's