Minimum Squares with Full Cuts

Problem Overview

Every cut must run straight across the whole current piece, from one edge to the opposite edge.

Intuition

Every cut must run straight across the whole current piece, from one edge to the opposite edge. On an n by m rectangle with n at most m, the only cut that frees a square takes an n by n square off the long side. Doing that as often as it fits removes m / n squares and leaves an n by (m mod n) rectangle. That is one step of the Euclidean algorithm for the GCD, so the total number of squares is the sum of the quotients it produces.

Algorithm

1Start the count at 0.
2While both sides are positive, swap them if needed so n is the shorter side.
3Add m / n to the count, since that many n by n squares come off the long side.
4Replace m with m mod n, the strip left over after those cuts.
5When one side reaches 0, the rectangle is fully cut. Return the count.

Example Walkthrough

Input: n = 4, m = 11

1. 11 / 4 gives two 4 by 4 squares, leaving a 4 by 3 rectangle.
2. 4 / 3 gives one 3 by 3 square, leaving a 3 by 1 rectangle.
3. 3 / 1 gives three 1 by 1 squares and the rectangle is gone.
4. The total is 2 + 1 + 3.

Output: 6

Common Pitfalls

• Subtracting one square per loop is the same idea, but it takes m / n steps instead of one division.
• Make sure the shorter side is the divisor on every step, or the quotient becomes 0 and nothing is cut.
• Full cuts mean you cannot carve a large square out of the middle, so the general tiling answer does not apply.
• The count never exceeds the longer side, so an int is enough.

Minimum Squares with Full Cuts.java

Java

// Approach: Every cut must run across the whole piece, so the best move is to
// cut off as many squares of the shorter side as fit. With sides n <= m that
// gives m / n squares and leaves an n by (m % n) rectangle. Repeating this is
// the Euclidean algorithm, and the answer is the sum of its quotients.
// Complexity: O(log(min(n, m))) time, O(1) space.
class Solution {

    public int minSquares(int n, int m) {
        int count = 0;

        while (n > 0 && m > 0) {
            if (n > m) {
                int temp = n;
                n = m;
                m = temp;
            }

            count += m / n;
            m %= n;
        }

        return count;
    }
}

Was this solution helpful?