Paths in Matrix Whose Sum Is Divisible by K

1
2
3
4
5
6
7
8

![](https://assets.leetcode.com/uploads/2022/08/13/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.

1
2
3
4
5
6

![](https://assets.leetcode.com/uploads/2022/08/17/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.

1
2
3
4
5
6

![](https://assets.leetcode.com/uploads/2022/08/12/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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <vector>
using namespace std;
class Solution {
public:
    int numberOfPaths(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size(), MOD = 1e9+7;
        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 r = 0; r < k; ++r) {
            if (i > 0) dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i-1][j][r]) % MOD;
            if (j > 0) dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i][j-1][r]) % 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

func numberOfPaths(grid [][]int, k int) int {
    m, n, MOD := len(grid), len(grid[0]), 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 r := 0; r < k; r++ {
                if i > 0 {
                    dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i-1][j][r]) % MOD
                }
                if j > 0 {
                    dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i][j-1][r]) % MOD
                }
            }
        }
    }
    return dp[m-1][n-1][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int numberOfPaths(int[][] grid, int k) {
        int m = grid.length, n = grid[0].length, MOD = 1_000_000_007;
        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 r = 0; r < k; r++) {
            if (i > 0) dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i-1][j][r]) % MOD;
            if (j > 0) dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i][j-1][r]) % MOD;
        }
        return dp[m-1][n-1][0];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun numberOfPaths(grid: Array<IntArray>, k: Int): Int {
        val m = grid.size; val n = grid[0].size; val MOD = 1_000_000_007
        val dp = Array(m) { Array(n) { IntArray(k) } }
        dp[0][0][grid[0][0]%k] = 1
        for (i in 0 until m) for (j in 0 until n) for (r in 0 until k) {
            if (i > 0) dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i-1][j][r]) % MOD
            if (j > 0) dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i][j-1][r]) % MOD
        }
        return dp[m-1][n-1][0]
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def numberOfPaths(grid: list[list[int]], k: int) -> int:
    m, n, MOD = len(grid), len(grid[0]), 10**9+7
    dp = [[[0]*k for _ in range(n)] for _ in range(m)]
    dp[0][0][grid[0][0]%k] = 1
    for i in range(m):
        for j in range(n):
            for r in range(k):
                if i > 0:
                    dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i-1][j][r]) % MOD
                if j > 0:
                    dp[i][j][(r+grid[i][j])%k] = (dp[i][j][(r+grid[i][j])%k] + dp[i][j-1][r]) % 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

fn number_of_paths(grid: Vec<Vec<i32>>, k: i32) -> i32 {
    let (m, n, k, MOD) = (grid.len(), grid[0].len(), k as usize, 1_000_000_007);
    let mut dp = vec![vec![vec![0; k]; n]; m];
    dp[0][0][(grid[0][0] % k as i32) as usize] = 1;
    for i in 0..m {
        for j in 0..n {
            for r in 0..k {
                let rem = ((r as i32 + grid[i][j]) % k as i32) as usize;
                if i > 0 {
                    dp[i][j][rem] = (dp[i][j][rem] + dp[i-1][j][r]) % MOD;
                }
                if j > 0 {
                    dp[i][j][rem] = (dp[i][j][rem] + dp[i][j-1][r]) % MOD;
                }
            }
        }
    }
    dp[m-1][n-1][0]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

function numberOfPaths(grid: number[][], k: number): number {
    const m = grid.length, n = grid[0].length, MOD = 1e9+7;
    const dp = Array.from({length: m}, () => Array.from({length: n}, () => Array(k).fill(0)));
    dp[0][0][grid[0][0]%k] = 1;
    for (let i = 0; i < m; i++) for (let j = 0; j < n; j++) for (let r = 0; r < k; r++) {
        const rem = (r + grid[i][j]) % k;
        if (i > 0) dp[i][j][rem] = (dp[i][j][rem] + dp[i-1][j][r]) % MOD;
        if (j > 0) dp[i][j][rem] = (dp[i][j][rem] + dp[i][j-1][r]) % MOD;
    }
    return dp[m-1][n-1][0];
}