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?

  • $\begingroup$ 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! $\endgroup$ – Raphael Feb 21 at 5:26

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.