Given a paper of size
A x B, the task is to cut the paper into squares of any size. Find the minimum number of squares that can be cut from the paper.
When paper size is
36 x 30, the output should be
5. An 36 x 30 paper can be cut into 3 squares of size 12 x 12 and 2 squares of size 18 x 1.
Please note that greedy approach doesn't always work. For example in the above example, greedy solution is 6, 1 square of size 30 x 30 and 5 squares of size 6 x 6.