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 piece of paper that she wants to cut into  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  piece of paper:
    example-cutting-squares.png

Given n and m, find and print the minimum number of cuts Mary must make to cut the paper into  squares that are  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   you need to make  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

1 comment

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]

Leave a Reply