Problem

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 byk. Since the answer may be very large, return it modulo 10^9 + 7.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|} \hline \colorbox{red}5 & \colorbox{red}2 & \colorbox{red}4 \\ \hline 3 & 0 & \colorbox{red}5 \\ \hline 0 & 7 & \colorbox{red}2 \\ \hline \end{array} \text{ } \Huge \begin{array}{|c|c|c|} \hline \colorbox{blue}5 & 2 & 4 \\ \hline \colorbox{blue}3 & \colorbox{blue} 0 & \colorbox{blue} 5 \\ \hline 0 & 7 & \colorbox{blue} 2 \\ \hline \end{array} $$

1
2
3
4
5

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

$$ \Huge \begin{array}{|c|c|} \hline \colorbox{red}0 & \colorbox{red}0 \\ \hline \end{array} $$

1
2
3

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

$$ \Huge \begin{array}{|c|c|c|c|} \hline 7 & 3 & 4 & 9 \\ \hline 2 & 3 & 6 & 2 \\ \hline 2 & 3 & 7 & 0 \\ \hline \end{array} $$

1
2
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 * 10^4
  • 1 <= m * n <= 5 * 10^4
  • 0 <= grid[i][j] <= 100
  • 1 <= k <= 50

Solution

Method 1 - 3D DP (Remainder DP)

Intuition

We need to count the number of paths from the top-left to the bottom-right of a grid, moving only right or down, such that the sum of the path is divisible by k. This is a classic DP problem: dp[i][j][r] = number of ways to reach (i, j) with sum % k == r.

Approach

Let dp[i][j][r] be the number of ways to reach cell (i, j) with sum % k == r. For each cell, we can come from the left or from above, and update the remainder accordingly. Use modulo 10^9 + 7 (denoted MOD) for the answer.

Code

 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];
}

Complexity

  • ⏰ Time complexity: O(m * n * k)
  • 🧺 Space complexity: O(m * n * k)