Need help to find out why my approach is failing for RECTSQ

general
,
1

Hi
I was trying to solve the problem RECTSQ, and somehow succeeded to solve it for the provided testcases, but codechef shows WA. Please help me to find the flaws in my approach or concept.
Since the squares must be of same dimensions, i understand that i have to maximize their side so the no of squares would be minimal.So, what i have done is:

  1. Find the smallest of the dimensions from the rectangle data(consider as @var small), since the side of the square cant be greater than any of the dimensions.

  2. Keep looping from ‘small’ upto 2, because i thought looping upto 1 would create the maximum no of squares.

  3. for each ‘i’ in the for loop, I check if the ‘i’ nearest to ‘small’ can create a square which perfectly divides the area and ‘break’ if it does, as that ‘i’ would be the greatest square possible.

    for (int i = small; i greaterthanequals 2; i–) {
    if (area % (i * i) == 0) {
    noOfSquares = area / (i * i);
    break;
    }
    }
    This is everything. Here’s the code.Thanks in advance.

1 Like
2

This approach would assume that a 8\times 6 plot could be broken up into 4\times 4 squares (which of course it can’t). You need to find the \gcd of the length and width for the largest packing square.

1 Like
3

Oh…i see… Well Thanks for your help. It means a lot. Thanks again.

1 Like