How to calculate Sub matrix of a matrix

Question

I was giving a test for a company called Code Nation and came across this question which asked me to calculate how many times a number k appears in the submatrix M[n][n]. Now there was a example which said Input like this.

5
1 2 3 2 5
36

M[i][j] is to calculated by a[i]*a[j] which on calculation turn I could calculate.

1,2,3,2,5
2,4,6,4,10
3,6,9,6,15
2,4,6,4,10
5,10,15,10,25

Now I had to calculate how many times 36 appears in sub matrix of M.

The answer was 5.

I am unable to comprehend how to calculate this submatrix. How to represent it? I had a naïve approach which resulted in many matrices of which I think none are correct.

One of them is Submatrix[i][j]

1 2 3  2  5
3 9 18 24 39
6 18 36 60 99
15 33 69 129 228
33 66 129 258 486

This was formed by adding all the numbers before it 0,0 to i,j

In this 36 did not appear 5 times so i know this is incorrect. If you can back it up with some pseudo code it will be icing on the cake.

Appreciate the help

[Edit] : Referred Following link 1 link 2

This question is poorly constructed. Consider stating the problem clearly and then separately describing your approach — WestCoastProjects, Mar 15 '15 at 09:29
@javadba i altered the question. Can you suggest any more improvements? — Saras Arya, Mar 18 '15 at 08:52

score 1 · Accepted Answer · edited Apr 13 '17 at 12:48

1

My guess is that you have to compute how many submatrices of M have sum equal to 36.

Here is Matlab code:

a=[1,2,3,2,5];
n=length(a);
M=a'*a;
count = 0;
for a0 = 1:n
    for b0 = 1:n
        for a1 = a0:n
            for b1 = b0:n
                A = M(a0:a1,b0:b1);
                if (sum(A(:))==36)
                    count = count + 1;
                end
            end
        end
    end
end
count

This prints out 5.

So you are correctly computing M, but then you have to consider every submatrix of M, for example, M is

1,2,3,2,5
2,4,6,4,10
3,6,9,6,15
2,4,6,4,10
5,10,15,10,25

so one possible submatrix is

1,2,3
2,4,6
3,6,9

and if you add up all of these, then the sum is equal to 36.

There is an answer on cstheory which gives an O(n^3) algorithm for this.

edited Apr 13 '17 at 12:48

Community

1
1

answered Mar 15 '15 at 09:29

Peter de Rivaz

33,126
4
46
75

The pseudocode I gave is O(n^6) (looks at O(n^4) submatrices, and each submatrix has O(n^2) elements), but the method in the linked answer is O(n^3). – Peter de Rivaz Mar 17 '15 at 11:52
The algorithm in the [link](https://cs.stackexchange.com/questions/18173/number-of-submatrices-with-a-particular-sum/) is not very intuitive can you give a pseudo code to explain it better – Saras Arya Mar 17 '15 at 19:18

How to calculate Sub matrix of a matrix

1 Answers1