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);

     }

}

Maximum height when coins are arranged in a triangle

public class MaxHghtToArrangeTri {

    

     /**

      *         *           ß 1 coin

      *   *         *       ß 2 coin

      * *      *          * ß 3 coin

      *

      * Coins need for Height H = 1 + 2 + 3 + ........ + H-1

      *                                 = H(H-1)/2

      * @param coins

      * @return

      */

     private static int getMaxHeight(int coins) {

          

           int d = (int)Math.pow((8*coins + 1),.5);

          

           int height = (d + 1)/2;

          

           return height-1;

     }

    

     /**

      * @param args

      */

     public static void main(String[] args) {

           int coins = 7;

           int maxHeight = getMaxHeight(coins);

          

           System.out.println(maxHeight);

     }

}