SmashCode - 1 year ago 73

Java Question

I have been working on problem where i need to split a rectangular grid(M*N) on to minimum number of square grids and let me give an idea i had with an example..

let us consider 8*5 grid . The first maximum element we can takeout is 5*5 it will be left out with 3*5 later the maximum rectangle we can take out is 3*3 later it comes 2*3 which we can split to 2 1*1 grid i need a better algorithm with less time complexity as the above mentioned algorithm takes more time....thanks in regards..

here is visuals of given problem statement..

Answer Source

This problem is equivalent to finding the GCD(greatest common divisor) of two number.

This is how we visual an example to find GCD of pair (200x117)

So, what we can do is using the classic Euclid algorithm:

if we have a rectangle size `(a,b) and a >= b`

-> create `a/b`

squares size `(b, b)`

and solve the sub problem of rectangle size `(b, a % b)`

and continue until we reach `(x, 0)`

Pseudo code

```
void gcd(int a, int b){
if(b == 0)
return;
print a/b squares with size b x b;
gcd(b, a % b);
}
```

Time complexity should be O(log max(a,b))

So, for case (5,4) , first, we create an square (4,4) -> what left if (4,1) -> create 4 squares size (1,1) -> (1, 0) -> return;