#1240

Tiling a Rectangle with the Fewest Squares

candidate master · 1360 · lc hard +32 · verified · 54.9% accepted · 721 likes · top 48%

⚑ Constraint Satisfaction (Sudoku / N-Queens)

Description

You are given a rectangle with dimensions n x m. Tile it completely using the fewest possible integer-sided squares. Return the minimum number of squares needed.

Example 1:

Input: n = 2, m = 3
Output: 3
Explanation: 3 squares are necessary to cover the rectangle.
2 (squares of 1x1)
1 (square of 2x2)

Example 2:

Input: n = 5, m = 8
Output: 5

Example 3:

Input: n = 11, m = 13
Output: 6

Code

1
2
3