# 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 '19 at 5:26

$$\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)$$