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.

Contributed by Berkan Teber

You are not signed in. You can only run/submit code after signing in. Create your free Codela account now!