Description#
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:
![](https://spcdn.pages.dev/leetcode/problems/2435.Paths%20in%20Matrix%20Whose%20Sum%20Is%20Divisible%20by%20K/images/image-20220813183124-1.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/2435.Paths%20in%20Matrix%20Whose%20Sum%20Is%20Divisible%20by%20K/images/image-20220817112930-3.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/2435.Paths%20in%20Matrix%20Whose%20Sum%20Is%20Divisible%20by%20K/images/image-20220812224605-3.png)
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
Solutions#
Solution 1: Memoization Search#
We design a function dfs(i, j, s)
to represent the number of paths starting from (i, j)
with an initial path sum modulo $k$ equal to $s$.
For each position $(i, j)$, we can choose to move right or down, so we have:
$$
dfs(i, j, s) = dfs(i + 1, j, (s + grid[i][j]) \bmod k) + dfs(i, j + 1, (s + grid[i][j]) \bmod k)
$$
The answer is dfs(0, 0, 0)
. We can use memoization search.
The time complexity is $O(m \times n \times k)$, and the space complexity is $O(m \times n \times k)$. Here, $m$ and $n$ are the number of rows and columns of the matrix, and $k$ is the given integer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
@cache
def dfs(i, j, s):
if i < 0 or i >= m or j < 0 or j >= n:
return 0
s = (s + grid[i][j]) % k
if i == m - 1 and j == n - 1:
return int(s == 0)
ans = dfs(i + 1, j, s) + dfs(i, j + 1, s)
return ans % mod
m, n = len(grid), len(grid[0])
mod = 10**9 + 7
ans = dfs(0, 0, 0)
dfs.cache_clear()
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
private int m;
private int n;
private int k;
private static final int MOD = (int) 1e9 + 7;
private int[][] grid;
private int[][][] f;
public int numberOfPaths(int[][] grid, int k) {
this.grid = grid;
this.k = k;
m = grid.length;
n = grid[0].length;
f = new int[m][n][k];
for (var a : f) {
for (var b : a) {
Arrays.fill(b, -1);
}
}
return dfs(0, 0, 0);
}
private int dfs(int i, int j, int s) {
if (i < 0 || i >= m || j < 0 || j >= n) {
return 0;
}
s = (s + grid[i][j]) % k;
if (f[i][j][s] != -1) {
return f[i][j][s];
}
if (i == m - 1 && j == n - 1) {
return s == 0 ? 1 : 0;
}
int ans = dfs(i + 1, j, s) + dfs(i, j + 1, s);
ans %= MOD;
f[i][j][s] = ans;
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int numberOfPaths(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
int mod = 1e9 + 7;
vector<vector<vector<int>>> f(m, vector<vector<int>>(n, vector<int>(k, -1)));
function<int(int, int, int)> dfs;
dfs = [&](int i, int j, int s) {
if (i < 0 || i >= m || j < 0 || j >= n) return 0;
s = (s + grid[i][j]) % k;
if (i == m - 1 && j == n - 1) return s == 0 ? 1 : 0;
if (f[i][j][s] != -1) return f[i][j][s];
int ans = dfs(i + 1, j, s) + dfs(i, j + 1, s);
ans %= mod;
f[i][j][s] = ans;
return ans;
};
return dfs(0, 0, 0);
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| func numberOfPaths(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
var mod int = 1e9 + 7
f := make([][][]int, m)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, k)
for x := 0; x < k; x++ {
f[i][j][x] = -1
}
}
}
var dfs func(i, j, s int) int
dfs = func(i, j, s int) int {
if i < 0 || i >= m || j < 0 || j >= n {
return 0
}
s = (s + grid[i][j]) % k
if i == m-1 && j == n-1 {
if s == 0 {
return 1
}
return 0
}
if f[i][j][s] != -1 {
return f[i][j][s]
}
ans := dfs(i+1, j, s) + dfs(i, j+1, s)
ans %= mod
f[i][j][s] = ans
return ans
}
return dfs(0, 0, 0)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| function numberOfPaths(grid: number[][], k: number): number {
const MOD = 10 ** 9 + 7;
const m = grid.length,
n = grid[0].length;
let ans = Array.from({ length: m + 1 }, () =>
Array.from({ length: n + 1 }, () => new Array(k).fill(0)),
);
ans[0][1][0] = 1;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let v = 0; v < k; v++) {
let key = (grid[i][j] + v) % k;
ans[i + 1][j + 1][key] =
(ans[i][j + 1][v] + ans[i + 1][j][v] + ans[i + 1][j + 1][key]) % MOD;
}
}
}
return ans[m][n][0];
}
|
Solution 2: Dynamic Programming#
We can also use dynamic programming to solve this problem.
Define the state $dp[i][j][s]$ to represent the number of paths from the starting point $(0, 0)$ to the position $(i, j)$, where the path sum modulo $k$ equals $s$.
The initial value is $dp[0][0][grid[0][0] \bmod k] = 1$, and the answer is $dp[m - 1][n - 1][0]$.
We can get the state transition equation:
$$
dp[i][j][s] = dp[i - 1][j][(s - grid[i][j])\bmod k] + dp[i][j - 1][(s - grid[i][j])\bmod k]
$$
The time complexity is $O(m \times n \times k)$, and the space complexity is $O(m \times n \times k)$. Here, $m$ and $n$ are the number of rows and columns of the matrix, and $k$ is the given integer.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution:
def numberOfPaths(self, grid: List[List[int]], k: int) -> int:
m, n = len(grid), len(grid[0])
dp = [[[0] * k for _ in range(n)] for _ in range(m)]
dp[0][0][grid[0][0] % k] = 1
mod = 10**9 + 7
for i in range(m):
for j in range(n):
for s in range(k):
t = ((s - grid[i][j] % k) + k) % k
if i:
dp[i][j][s] += dp[i - 1][j][t]
if j:
dp[i][j][s] += dp[i][j - 1][t]
dp[i][j][s] %= mod
return dp[-1][-1][0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
private static final int MOD = (int) 1e9 + 7;
public int numberOfPaths(int[][] grid, int k) {
int m = grid.length, n = grid[0].length;
int[][][] dp = new int[m][n][k];
dp[0][0][grid[0][0] % k] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int s = 0; s < k; ++s) {
int t = ((s - grid[i][j] % k) + k) % k;
if (i > 0) {
dp[i][j][s] += dp[i - 1][j][t];
}
if (j > 0) {
dp[i][j][s] += dp[i][j - 1][t];
}
dp[i][j][s] %= MOD;
}
}
}
return dp[m - 1][n - 1][0];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
const int mod = 1e9 + 7;
int numberOfPaths(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size();
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(k)));
dp[0][0][grid[0][0] % k] = 1;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
for (int s = 0; s < k; ++s) {
int t = ((s - grid[i][j] % k) + k) % k;
if (i) dp[i][j][s] += dp[i - 1][j][t];
if (j) dp[i][j][s] += dp[i][j - 1][t];
dp[i][j][s] %= mod;
}
}
}
return dp[m - 1][n - 1][0];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| func numberOfPaths(grid [][]int, k int) int {
m, n := len(grid), len(grid[0])
var mod int = 1e9 + 7
dp := make([][][]int, m)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, k)
}
}
dp[0][0][grid[0][0]%k] = 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
for s := 0; s < k; s++ {
t := ((s - grid[i][j]%k) + k) % k
if i > 0 {
dp[i][j][s] += dp[i-1][j][t]
}
if j > 0 {
dp[i][j][s] += dp[i][j-1][t]
}
dp[i][j][s] %= mod
}
}
}
return dp[m-1][n-1][0]
}
|