number of square matrices in a non-square matrix [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Software Engineering Stack Exchange.

Closed 5 years ago.

Improve this question

i was wondering if there is any formula to calculate the number of square matrices present in a square matrix.

e.g

• a 3x2 matrix has 3 square matrices that are (2x2, 1x1, 1x1)
• a 6x3 matrix has 2 square matrices that are (3x3, 3x3)
• a 4x3 matrix has 4 square matrices that are (3x3, 1x1, 1x1, 1x1)

any idea how to get this ? Thanks in advance

Answer 1

Well, at a glance it seems like you want the "greedy" solution that finds the largest possible squares (rather than using all 1x1s), so it seems like simply finding the largest possible square in the current matrix and then recursively looking at the remaining part of the matrix should work:

int squaresInRectangle(int m, int n) {
   if(m <= 0 || n <= 0) { return 0; }
   int largestPossibleSquareSize = min(m, n);
   int remainingSquareCount;
   if(m < n) {
       remainingSquareCount = squaresInRectangle(m, n - largestPossibleSquareSize);
   } else {
       remainingSquareCount = squaresInRectangle(m - largestPossibleSquareSize, n);
   }
   return 1 + remainingSquareCount;
}

Answer 2

Many problems can be solved with a recursive greedy algorithm.

Given a MxN matrix, you can always find a KxK matrix in the upper left corner, where K = Min(M,N). If you then remove that part out from your matrix, you get a remainder. Repeat the process on that matrix until you run out of elements.

An example execution of the naive algorithm:

|0 0 0 1 1| => |0 0 0| % |1 1|
|0 0 0 1 1|    |0 0 0|   |1 1|
|0 0 0 2 3|    |0 0 0|   |2 3|

There's still a matrix remainder.

|1 1| => |1 1| %  |2 3|
|1 1|    |1 1|
|2 3|

There's still a matrix remainder.

|2 3| => |2| % |3|

There's still a matrix remainder.

|3| => |3| % ||

It appears we're done, having run out of matrices. One 3x3, one 2x2, two 1x1.

And remember, if you lift homework solutions from somewhere without understanding them and without being able to motivate what you've said in your report, the person you're cheating most is yourself.

Answer 3

Very similar to the Euclidean algorithm

int squaresInRectangle(int m, int n) {
    if (n <= 0) { return 0; }
    return squaresInRectangle(n, m % n) + (m / n);
}