CareerCup

Like the others have mentioned, the greedy approach does not work. Below is a dynamic programming based approach.

1. Lets say we have a rectangle with dimensions i and j. We cut a square of size k*k.
2. After the above k sized square is removed, we can have the below 2 options
a) Rectangle (i-k,k) & Rectangle (i, j-k)
b) Or Rectangle(i-k,j) & Rectangle(k, j-k)
3. Take the min of (a) and (b)

Repeat the process for all values of k. Below is an iterative implementation

public static int minSquares(int x, int y) {
    int[][] partial_solutions = new int[x+1][y+1];

    for (int i=0; i<=x; i++) {
      for (int j=0; j<=y; j++) {
        if (i==0 || j==0) {
          partial_solutions[i][j] = 0;
          continue;
        }
        if (i==j) {
          partial_solutions[i][j] = 1;
          continue;
        }
        if (x%y == 0) {
          partial_solutions[x][y] = x/y;
          continue;
        }
        if (y%x == 0) {
          partial_solutions[x][y] = y/x;
          continue;
        }


        int smaller = Math.min(i, j);
        int min = Integer.MAX_VALUE;
        for (int k=1; k<=smaller; k++) {
          int minK = Math.min(partial_solutions[i-k][j] + partial_solutions[k][j-k], partial_solutions[i][j-k]+partial_solutions[i-k][k]);
          min = Math.min(min, minK);
        }
        partial_solutions[i][j] = 1+min;
      }
    }

    return partial_solutions[x][y];
  }

With no loss of generality, we can assume A <= B for all cases.

We can then compute the minimum number of squares formed by the recursive method:

recursiveCompute(A, B):
   if A == B then: return 1;
   if A == 1 then: return B;
   return (B/A) + recursiveCompute((B%A), A);

Note that B/A here is integer division (e.g. 7/2 = 3)

In your 13 x 29 example, you have:

recursiveCompute(13, 29) = (29/13) + recursiveCompute(3, 13)
= 2 + (13/3) + recursiveCompute(1, 3)
= 2 + 4 + 3
= 9

Note the similarity to Euclid's GCD computing algorithm!

EDIT: edited my answer per sw's comment on A = B case. Thanks!

The greedy solution is not correct. Counterexample 5x6.

this can NOT be solved using greedy aproach
consider paper 1000x1001 size, you cat one square 1000x1000 and you are left with 1000 smaller rectangles
another example, paper 6x5, greedy solution will give 6 squares, when optimal is 5 (two 3x3 and three 2x2 squares)
Still thinking about correct solution

The greedy approach doesn't work. Counterexample is 5x6.

Non greedy approach. Given solution for all (m,n) smaller than M,N, you can simply try all squares that fit and use the solution of the sub problems to cover the remaining. So it's O(M*N) subproblems, each with O(min(M,N)) non-recursive work

Recursive solution, which is using dynamic programming - check all possible squares recursively and find the one which gives optimal count of squares.
Got result=5 for 5x6 and result=20 for 1000x1001 (not sure how to test that this is really the optimal division)

import java.util.HashMap;
import java.util.Map;

public class OptimalSquare {
	public OptimalSquare(){
		int n=1000;
		int m=1001;
		Map<String,Integer> saveMin = new HashMap<>();
		int result = findMin(n,m,saveMin);
		System.out.println("n="+n+" m="+m+" result="+result);
		
		saveMin = new HashMap<>();
		n=5;
		m=6;
		result = findMin(n,m,saveMin);
		System.out.println("n="+n+" m="+m+" result="+result);
		
		saveMin = new HashMap<>();
		n=5;
		m=4;
		result = findMin(n,m,saveMin);
		System.out.println("n="+n+" m="+m+" result="+result);
	}
	
	private int findMin(int n, int m, Map<String,Integer> saveMin){
		int count = 0;
		int minSoFar = Integer.MAX_VALUE;
		if(n==0 || m==0) return 0;
		if (n==m){
			String key = n+","+m;
			saveMin.put(key, 1);
			return 1;
		}
		int min = m>n?n:m;
		int max = m>n?m:n;
		String key = min+","+max;
		if(saveMin.containsKey(key)) return saveMin.get(key);
		if(min==1){
			saveMin.put(key, max);
			return max;
		}
		for(int size=min;size>0;size--){
			int squares = max/size;
			count = squares+findMin(max-(squares*size),size,saveMin)+findMin(max,min-size,saveMin);
			minSoFar = Math.min(minSoFar, count);
		}
		saveMin.put(key, minSoFar);
		return minSoFar;
	}
}

1000x1001 can be cut to 16 pieces, not 20.

Cutting 1000x1001 horizontal. Two pieces are: 1000x625 and 1000x376
Cutting 1000x625 horizontal. Two pieces are: 625x625 and 625x375
1 pieces of 625x625 located on 625x625
Cutting 625x375 horizontal. Two pieces are: 375x375 and 375x250
1 pieces of 375x375 located on 375x375
Cutting 375x250 horizontal. Two pieces are: 250x250 and 250x125
1 pieces of 250x250 located on 250x250
2 pieces of 125x125 located on 250x125
Cutting 1000x376 horizontal. Two pieces are: 376x752 and 376x248
2 pieces of 376x376 located on 376x752
Cutting 376x248 horizontal. Two pieces are: 248x248 and 248x128
1 pieces of 248x248 located on 248x248
Cutting 248x128 horizontal. Two pieces are: 128x128 and 128x120
1 pieces of 128x128 located on 128x128
Cutting 128x120 horizontal. Two pieces are: 120x80 and 120x48
Cutting 120x80 horizontal. Two pieces are: 80x80 and 80x40
1 pieces of 80x80 located on 80x80
2 pieces of 40x40 located on 80x40
Cutting 120x48 horizontal. Two pieces are: 48x96 and 48x24
2 pieces of 48x48 located on 48x96
2 pieces of 24x24 located on 48x24

FINAL:
625x625: 1 pieces
375x375: 1 pieces
250x250: 1 pieces
125x125: 2 pieces
376x376: 2 pieces
248x248: 1 pieces
128x128: 1 pieces
80x80: 1 pieces
40x40: 2 pieces
48x48: 2 pieces
24x24: 2 pieces
Sanity check:
Projected area 1001000, all pieces added together: 1001000

public class MinSquares {

static int w =5;
static int l=4;

public static void main(String [] args){
int numOfSquares = 0;
while(w != 0 && l != 0){
if(w > l){
numOfSquares++;
w = w-l;
}
else{
numOfSquares++;
l= l-w;
}
}
System.out.println(numOfSquares);
}

}

If you want the min squares number there is only one choice: you have to take the maximum area.

public void testSquare ( int a, int b){
            int max = Math.max(a, b);
            int min = Math.min(a, b);
            int number = 0;
            Map<String, Integer> squarePerSize = new HashMap<>();
            while (max > 0 && min > 0) {
                int less = max - min;
                String key = min + "x" + min;
                Integer j = squarePerSize.getOrDefault(key, 0);
                squarePerSize.put(key, j + 1);
                max = Math.max(min, less);
                min = Math.min(min, less);
                number++;
            }
            for (Map.Entry<String, Integer> stringIntegerEntry : squarePerSize.entrySet()) {
                System.out.println(stringIntegerEntry.getKey() + ":" + stringIntegerEntry.getValue());
            }
            System.out.println("total:" + number);
        }

using namespace std;


// Returns length of the longest substring
// with equal number of zeros and ones.

int stringLen(string str)
{

// Create a map to store differences

// between counts of 1s and 0s.

map<int, int> m;



// Initially difference is 0.

m[0] = -1;



int count_0 = 0, count_1 = 0;

int res = 0;

for (int i=0; i<str.size(); i++)

{

// Keeping track of counts of

// 0s and 1s.

if (str[i] == '0')

count_0++;

else

count_1++;



// If difference between current counts

// already exists, then substring between

// previous and current index has same

// no. of 0s and 1s. Update result if this

// substring is more than current result.

if (m.find(count_1 - count_0) != m.end())

res = max(res, i - m[count_1 - count_0]);



// If current difference is seen first time.

else

m[count_1 - count_0] = i;

}



return res;
}


// driver function

int main()
{

string str = "101001000";

cout << "Length of longest balanced"

" sub string = ";

cout << stringLen(str);

return 0;
}

using namespace std;


// Returns length of the longest substring
// with equal number of zeros and ones.

int stringLen(string str)
{

// Create a map to store differences

// between counts of 1s and 0s.

map<int, int> m;



// Initially difference is 0.

m[0] = -1;



int count_0 = 0, count_1 = 0;

int res = 0;

for (int i=0; i<str.size(); i++)

{

// Keeping track of counts of

// 0s and 1s.

if (str[i] == '0')

count_0++;

else

count_1++;



// If difference between current counts

// already exists, then substring between

// previous and current index has same

// no. of 0s and 1s. Update result if this

// substring is more than current result.

if (m.find(count_1 - count_0) != m.end())

res = max(res, i - m[count_1 - count_0]);



// If current difference is seen first time.

else

m[count_1 - count_0] = i;

}



return res;
}


// driver function

int main()
{

string str = "101001000";

cout << "Length of longest balanced"

" sub string = ";

cout << stringLen(str);

return 0;
}

static int findMinCuts(int i, int j) {
	    if(i == j)
	        return 1;
	    if(i == 0 || j == 0)
	        return 0;
	    if(dp[i][j] != -1)
	        return dp[i][j];
	    int minValue = Math.min(i, j);
	    int ans = Integer.MAX_VALUE;
	    for(int k = 1; k <= minValue; k++) {
	        ans = Math.min(ans, Math.min(findMinCuts(i - k, k) + findMinCuts(i, j - k), findMinCuts(i - k, j) + findMinCuts(k, j - k)));
	    }
	    return dp[i][j] = 1 + ans;
	 }

n

{{lijljnl}}

Can be solved using greedy approach.

can be solved using greedy approach.

can be solved using greedy approach

int MaxNumSqures( int  a , int b ){
	if( !a || !b )
	    return 0;
	if( a < b )
		return MaxNumSquares( b , a );
	return a / b + MaxNumSquares( b , a % b );
}

int maxSquares( int a , int b ){
	if( !a || !b )
		return 0;
	if( a < b )
		return maxSquares( b , a );
	return a / b + maxSquares( b , a % b );
}