Given a 2d array(matrix), find number of sub-matrices whose sum is divisible by p.

general
,
1

Given a matrix, find number of sub-matrices whose sum is divisible by p.

Size of matrix= n x m
Constraints:

1 <= n,m,p <= 200

example:
n = 2, m =2, p=2
Matrix:

1 2

3 4

Ans = 5

Any thoughts on how to solve this without brute force?

2

What is the expected Complexity?

3

Think of the 1D version first. Given array of size n, you want to know how many subarrays have sum divisible by p. We can solve this in O(n). Tip: get all prefix sums and put them to a frequency table for every mod.

If you can do that much, you can extend problem to 2D smoothly. Brute force every pair of rows. Make a 1D array of columns out of the sum of elements between each pair of rows. Solve the 1D version then you’re done.

There are O(n^2) pairs of rows and the 1D subproblem is O(n). Total is O(n^3). This is sufficient to pass the time limit.

5 Likes
4

less than O(n^3)

5

thanks… It took me some time to solve the 1-D version but eventually I was able to do it.