Hint-1 : Think about the time constraints.

Hint-2 : Can we do something with **gcd** ?

From the given constraints we can pick two elements $N$ and $M$ in O($n^2$) time. Let’s say the height of the grid is $M$. To cover the full length of the height we have to select some shape which can divide the length. For instance, if height is 8, we can select 1,2,4, and 8 size shapes to cover the full length of height. Same goes for the width. If we choose 6 as width. We can cover the length of the width using 1,2,3, and 6 size shapes. Now we know how to cover the height and width individually. Can we calculate the answer for $8 * 6$ grid now???

Easy peasy. Just take all the common divisors between height and width. For efficient solution we just have to calculate the greatest common divisor of the two selected number and finding it’s number of divisors. After that we just have to find the maximum number of divisors among all possible pairs. For the above instance, the common divisors are 1 and 2.

Toph uses cookies. By continuing you agree to our Cookie Policy.