2435

2435. Paths in Matrix Whose Sum Is Divisible by K (Hard)

You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right.

Return the number of paths where the sum of the elements on the path is divisible by k. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: There are two paths where the sum of the elements on the path is divisible by k.
The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3.
The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.

Example 2:

Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.

Example 3:

Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.

 

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 5 * 104
• 1 <= m * n <= 5 * 104
• 0 <= grid[i][j] <= 100
• 1 <= k <= 50

Companies: Google

Related Topics:
Array, Dynamic Programming, Matrix

Similar Questions:

• Unique Paths (Medium)
• Unique Paths II (Medium)
• Minimum Path Sum (Medium)
• Dungeon Game (Hard)
• Cherry Pickup (Hard)
• Shortest Path in Binary Matrix (Medium)
• Minimum Cost Homecoming of a Robot in a Grid (Medium)
• Check if There is a Path With Equal Number of 0's And 1's (Medium)

Solution 1. DP

Let dp[i][j] be all the sums of paths from (0,0) to (i,j).

dp[i][j] = { x + A[i][j] | x is in dp[i-1][j] and dp[i][j-1] }

dp[0][0] = { A[0][0] }

Instead of keeping track of the set of sum numbers, we just need to keep track of the count of sum % K.

So, we let each dp[i][j] be an array, where dp[i][j][k] is the count of the count of paths from (0,0) to (i,j) that have sum % K == k.

dp[0][0][k] = 1 if k == A[i][j] % K
              0 otherwise

dp[i][j][k] = dp[i-1][j][k - A[i][j]] + dp[i][j-1][k - A[i][j]]

Since dp[i][j] only depends on dp[i-1][j] and dp[i][j-1], we can reduce the space complexity from O(MNK) to O(NK).

// OJ: https://leetcode.com/problems/paths-in-matrix-whose-sum-is-divisible-by-k
// Author: github.com/lzl124631x
// Time: O(MNK)
// Space: O(NK)
class Solution {
public:
    int numberOfPaths(vector<vector<int>>& A, int K) {
        long M = A.size(), N = A[0].size(), mod = 1e9 + 7;
        vector<vector<long>> dp(N, vector<long>(K));
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == 0 && j == 0) dp[j][A[i][j] % K]++;
                else {
                    vector<long> next(K);
                    for (int k = 0; k < K; ++k) next[k] = dp[j][(K + k - A[i][j] % K) % K];
                    if (j > 0) {
                        for (int k = 0; k < K; ++k) next[k] = (next[k] + dp[j - 1][(K + k - A[i][j] % K) % K]) % mod;
                    }
                    swap(next, dp[j]);
                }
            }
        }
        return dp[N - 1][0];
    }
};