How x*y for each cell to be part of an submatrix

#1

In the video the no. times each cell will be part of an submatrix is given by xy where x=(i+1)(j+1) and y=(n-i)*(m-j)

shouldn’t this be xcr

#2

Hey @sagar_aggarwal why do you think it should be XOR ?

#3

not XOR but x c y as per permutation and combinations

#4

See the main idea behind this problem is suppose the index of an element be (X, Y) in 0 based indexing, then the number of submatrices (Sx, y) for this element will be in can be given by the formula Sx, y = (X + 1) * (Y + 1) * (N – X) * (N – Y) . This formula works, because we just have to choose two different positions on the matrix that will create a submatrix that envelopes the element. Thus, for each element, ‘sum’ can be updated as sum += (Sx, y) * Arrx, y .
Moreover as you are saying that it should have been xCy , in this it will be choosing y in x elements.

#5

will this work in non square matrix where number of row is not equal to number of coloumn

#6

No, this implementation is only applicable to solve nxn matrix, moreover if you still have any doubt in this implementation. Watch this https://youtu.be/trhm1IuqSdA it will clear your all doubts.