-1

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

5
  • Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask
    – gnat
    Commented May 18, 2015 at 6:10
  • i was not able to solve this that is the reason why i needed help to solve the program and no offence if you know the answer then answer else just ignore. @gnat
    – Zishnu
    Commented May 18, 2015 at 6:16
  • @Zishnu Sadly, ignoring questions that is not quite up to par is very detrimental to the quality of the site. Anyway, there appears to be ambiguities in your question; for any matrix larger than 1x1, there are multiple solutions. Do you care about which one is chosen? Commented May 18, 2015 at 6:58
  • 1
    Please edit your question and clarify the ambiguities. Which of the multiple solutions are you looking for? Why do you write "present in a square matrix", but in your examples, the outer matrixes are rectangulars, not squares? If you do not edit your question, you are at risk for getting your question closed for beein unclear.
    – Doc Brown
    Commented May 18, 2015 at 7:27
  • 1
    I'm voting to close this question as off-topic because it is a request for code and appears to be a homework assignment.
    – maple_shaft
    Commented May 18, 2015 at 11:48

3 Answers 3

0

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;
}
0

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.

-2

Very similar to the Euclidean algorithm

int squaresInRectangle(int m, int n) {
    if (n <= 0) { return 0; }
    return squaresInRectangle(n, m % n) + (m / n);
}
2
  • Programmers is about conceptual questions and answers are expected to explain things. Throwing code dumps instead of explanation is like copying code from IDE to whiteboard: it may look familiar and even sometimes be understandable, but it feels weird... just weird. Whiteboard doesn't have compiler
    – gnat
    Commented May 18, 2015 at 9:10
  • The same algorithm that is on board. Just do not throw error
    – botanegg
    Commented May 18, 2015 at 11:52

Not the answer you're looking for? Browse other questions tagged or ask your own question.