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

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?

What is the expected Complexity?

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.

4 Likes

less than O(n^3)

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