Partition a given rectangle into minimum no. of squares

I was going through the following question

Given a paper of size A x B. Task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.

I tried writing a dp and a greedy solution for this problem, but none of them worked. Unfortunately the site from where I am practising this question also does not have a correct solution. Can someone please suggest a solution to this problem or is this also NP-hard like polygon partition ?

Complete Problem Statement

Read about euclid gcd algorithm for details.

Repeat this until B!=0:
Ans += A/B
A, B = B, A%B

Try to prove how. Just see, that i try to make squares of size B, A/B is number of squares i am able to make, and last line counts number of suares required to cover area, which couldnt be covered in squares of side B.

This approach is not optimal for all cases

you are right… Its not optimal

30 35
can be decomposed into
20*20 + 15*15 + 15*15 + 10*10 + 10*10

for calculating result of
30 35
can we calculate result for
6 7 ?
will it give same results ??

My mistake.

Some sort of DP solution must be there.

1 Like