# Carpet into Box

Given a carpet of size a * b [length * breadth] and a box of size c * d, one has to fit the carpet in the box in the minimum number of moves. A move is to fold the carpet in half, either by length or breadth.

One can even turn the carpet by 90 degrees any number of times, won’t be counted as a move.

Example: Box = 6 * 10 Carpet = 8 * 12

Output: No of moves = 1

Fold the carpet by breadth, 12/2 so now carpet is 6*8 and can fit fine.

My approach is to divide a larger side and see if it fits in to the box.and keep doing it.Is my approach valid?

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Feb 21 at 5:26

## 1 Answer

I am afraid your approach does not work.

Here is a counterexample. Box = 3 * 10 while Carpet = 4 * 8. One move is enough as you can fold the carpet by its width, reaching 2 * 8. If you fold the carpet by its length, 4 * 4 cannot fit into 3 * 10.

Here is the answer.

$$\min(\lceil\log_2\frac{a}{c}\rceil+\lceil\log_2\frac{b}{d}\rceil,\ \lceil\log_2\frac{b}{c}\rceil+\lceil\log_2\frac{a}{d}\rceil)$$

By the way, "length" refers usually to the longer side of a rectangle while "width" the shorter side.

• So we don't have to rotate carpet every time we halve the length. Just doing it on the first time is enough. – Manoharsinh Rana Feb 22 at 8:24