Minimum Number of Folds Problem in Python

By Abirami Somasundaram

To obtain the minimum number of folds to be taken on a paper of dimensions (height x width) to obtain the new dimensions (height x width) entered by the user.

Minimum Folding problem is where, using the original dimensions of a piece of paper height(h) and width(w) entered by the user, the minimum number of folds to be done to obtain the new dimensions height(h1) and width(h2) is to be estimated.

For example,

given (h,w)=9,4, we are to fold the paper until it is height and width are (h1,w1) 1 and 2 respectively.

1. First fold along the long edge, 4 units from the side resulting in a paper that is 5*4.

2. Next, we fold along the long edge, 2 units from the side, resulting in a paper that is 3*4. 

3. Next we fold along the same edge this time only 2 units resulting in 1*4 where the new height dimension is obtained.

4. To obtain the desired width along the center horizontally to achieve 1*2 in four folds.

A simple while loop traversal over the divide and conquer rule would help in obtaining the solution in the most optimal way.