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 void
main(String[] args) {

int len = 13, wid = 29;

int minSqr =

*getMinNumSqr*(len,wid);
System.

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

}

## No comments:

## Post a Comment