Perfect Squares
Real-world version: Fewest Square TilesThe statement here is our own: the same inputs, outputs and technique.
A courtyard crew paves a strip whose surface measures exactly area square metres. The
supplier stocks square slabs in every whole-metre side length: 1 by 1, 2 by 2, 3 by 3 and so
on, in unlimited quantity, and a slab of side s covers s * s square metres.
The crew lays slabs so that the covered surface adds up to area with nothing left over and
nothing overlapping. Only the areas matter here, not how the slabs sit next to each other,
and the same side length may be used as often as needed.
Given area, return the smallest number of slabs whose areas add up to exactly area.
Examples
Example 1
- Input
- area = 28
- Output
- 4
Three slabs of side 2 and one of side 4 cover 4 + 4 + 4 + 16, which is 28 square metres with four slabs.
Example 2
- Input
- area = 18
- Output
- 2
Two slabs of side 3 cover 9 + 9, which is exactly 18 square metres.
Constraints
- 1 <= area <= 10^4
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_tiles(area: int) -> int:public int fewestSquareTiles(int area)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 12 test cases: 12 passed
- Passed: 2 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