# Cut The Paper

Posted: 8 Jan, 2021

Difficulty: Hard

#### You are given a paper with dimension N * M. Your task is to find the minimum number of squares in which you can cut the given paper.

#### Note:

```
1. Square is a quadrilateral whose all four sides are of equal length.
2. If the given paper is already a square then it is possible to cut the whole square in one move.
```

##### Input Format:

```
The first line of the input contains an integer T, denoting the number of test cases.
The first line of each test case consists of two space-separated integers N and M denoting the dimensions of the given paper, in a separate line.
```

##### Output Format:

```
For each test case return, the minimum number of squares in which you can cut the given paper.
```

##### Note:

```
You don't have to print anything, it has already been taken care of. Just Implement the given function.
```

##### Constraints:

```
1<= T <= 50
1<= N, M <= 150
Time Limit: 1 sec.
```

Approach 1

- In order to try all possible ways to cut the paper, we make a recursive function that will compute the answer for the given (N, M).
- The base condition for this function will be when N==M (which means it is already a square), we will return 1 in such a case.
- In the case where the base condition is not satisfied, we will try out all possible ways to cut the paper horizontally and vertically as follows:
- For trying all possible horizontal cuts, we will find the answer for paper with dimensions (N-x, M) and (x, M) for x in the range from 1 to N/2(both inclusive) with the help of the same recursive function. And the summation of results from both calls for a given x will give one of the possible solutions.
- For trying all possible vertical cuts, we will find the answer for paper with dimensions (N, M-x) and (N, x) for x in the range from 1 to M/2(both inclusive) with the help of the same recursive function. And the summation of results from both calls for a given x will give one of the possible solutions.

- Taking the minimum of all possible solutions for given (N, M) will give the desired solution.
- One thing to observe here is that we can reach a state more than once for eg. the state (N-2, M-1) can be reached from (N-2, M) and (N-1, M-1).
- In order to avoid recomputation of solutions for a given state, we can use a 2-Dimensional table to store the results for a state, so that we can use those results for future calls to that state.
- There is one edge case for paper with dimension 13*11. Our algorithm will give 8 as the answer but since we can cut the paper in 6 squares only as shown in the following picture.

Eg. For paper with dimension (2, 3), the algorithm will work as follows:

- HELPER(2, 3)
- HELPER(1, 3)
- HELPER(1,2)
- HELPER(1,1)
- Return 1 ....(1)

- HELPER(1,1) // already computed
- Return 1 ....(2)

- Return 2 (sum of (1) + (2)) ….(3)

- HELPER(1,1)
- HELPER(1,1) // already computed
- Return 1 ….(4)

- Return 3 (sum of (3) + (4)) ….(5)

- HELPER(1,2)
- HELPER(1, 3) // already computed
- Return 3 ….(6)

- HELPER(2, 1)
- HELPER(1,1) // already computed
- Return 1 ….(7)

- HELPER(1,1) // already computed
- Return 1 ….(8)

- Return 2 (sum of (7) + (8)) ….(9)

- HELPER(1,1) // already computed
- HELPER(2,2)
- Return 1 // N==M ….(10)

- Return 3 // min(sum of (5) + (6), sum of (9,10))

- HELPER(1, 3)