Hint-1 : Think about the time constraints.

Hint-2 : Can we do something with gcd ?

From the given constraints we can pick two elements NN and MM in O(n2n^2) time. Let’s say the height of the grid is MM. 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 868 * 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.


10% Solution Ratio
Danial009Earliest, Jun '23
Danial009Fastest, 0.2s
Danial009Lightest, 5.7 MB
Danial009Shortest, 688B
Toph uses cookies. By continuing you agree to our Cookie Policy.