Last Updated: 8 Jan, 2021

Cut The Paper

Hard

Asked in company

Solve now

Problem statement

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.

Solve now

Approaches

01 Approach

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) // already computed
    - Return 1 ….(4)
  - Return 3 (sum of (3) + (4)) ….(5)
- 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(2,2)
  - Return 1 // N==M ….(10)
- Return 3 // min(sum of (5) + (6), sum of (9,10))

Solve now