# HackerRank – Cutting Paper Squares

How ever much I like paper, rock and scissor we only use paper and scissor in the problem of cutting paper squares.  The problem reads

Mary has an $m \times n$ piece of paper that she wants to cut into $1 \times 1$ pieces according to the following rules:

• She can only cut one piece of paper at a time, meaning she cannot fold the paper or layer already-cut pieces on top of one another.
• Each cut is a straight line from one side of the paper to the other side of the paper. For example, the diagram below depicts the three possible ways to cut a $3\times 2$ piece of paper:

Given n and m, find and print the minimum number of cuts Mary must make to cut the paper into $n\cdot m$ squares that are $1 \times 1$ unit in size.

## Cutting Paper squares – Solving the math

The best way to get to a solution is looking at the problem in this way. Every time you cut the paper, you add 1 to the total number of pieces of paper. Since you start with 1 and need to end with $n\cdot m$  you need to make $(n\cdot m) - 1$ cuts. I must admit that it took me a while before I realized that, but once you say that out loud it is pretty easy.

## Implementation

The input size of n and m are up to one billion, which makes the solutions potentially big. However, since we are using Python we don’t have to worry about variable size as we would have if we where using c# or Java.

The implementation is really trivial one line in the function we should complete. It looks like

def solve(n, m):
return n * m - 1

### Posted by Kristian

Jean-Marie Hachey

Cutting paper squares (Beginning Square Size: 3 by 1)

1) Order of squares (S1, S2, S3) not considered:
S1—S2—S3

Cut #1 gives:
S1 S2—S3

Cut #2 gives:
S1 S2 S3

Total of cuts: 2
[(nm) – 1 = 31 -1 = 2]

2) Order of squares (S1, S2, S3 ) considered:
S1—S2—S3

Cut #1 gives:
S1—S2 S3

Cut #2 gives:
S1 S2 S3

S1—S2—S3:
Cut #3 gives:
S1 S2—S3

Cut #4 gives:
S1 S2 S3

Total of cuts: 4
[(nm) + 1 = 31 +1 = 4]

Lucky

What if you can put the cut peices together and cut them together.