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
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.