Cut Paper into Minimum Number of Squares

Given a paper of size L x W, cut the paper into squares of any size and the count of the squares should be minimum.

Examples:

Input: 4 x 5

Output: 5

Explanation:

1 (squares of size 4x4) +

4 (squares of size 1x1)

Think that if we want to cut minimum number of squares from the paper then we would have to cut largest square possible from the paper first and largest possible square will contain the side as smaller side of the paper. Same operation will perform recursively on remaining paper.

public class MinNumSqr {

    

     private static int getMinNumSqr(int len, int wid) {

           int count = 0;

          

           if(wid>len) {

                int tmp = len;

                len = wid;

                wid = tmp;

           }

           while(wid>0) {

                count = count + len/wid;

               

                int rem = len % wid;

                len = wid;

                wid = rem;

           }

          

           return count;

     }   

    

     public static voidmain(String[] args) {

           int len = 13, wid = 29;

           int minSqr = getMinNumSqr(len,wid);

           System.out.println("Min Number of square#"+ minSqr);

     }

}