Cut The Paper

Hard
0/120
Average time to solve is 10m
7 upvotes
Asked in company
Google inc

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.
Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
2 3
Sample Output 1:
3
Explanation of sample input 1:
We can cut one square with side 2 and two squares with side 1.
Sample Input 2:
1
13 11
Sample Output 2:
6
Explanation of sample input 2:

alt-text

As given in the picture we can cut 5 squares out of paper with dimension 13*11.
Hint

Try all possible ways to cut the paper.

Approaches (1)
Dp Solution
  • 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))
Time Complexity

O(M*N^2 + N*M^2), where N and M are the dimensions of a given paper.

 

As there is N*M number of different pairs of (N, M), it takes O(N*M) order of time to compute the answer for all possible (N, M) states.

Also for calculating the answer for a state (N, M) it requires extra (N + M) operations.

Hence overall it takes O(M*N^2 + N*M^2) order of operations.

Space Complexity

O(N*M), where N and M are the dimensions of a given paper.

 

As we are storing answers for all pairs (N, M), hence it takes O(N*M) order of memory.

Code Solution
(100% EXP penalty)
Cut The Paper
Full screen
Console