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?

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.