Paths in Matrix Whose Sum Is Divisible by K

hard dynamic programming matrix modular arithmetic

Problem

You start at the top-left cell (0, 0) of an m × n grid and want to reach the bottom-right cell (m−1, n−1), moving only down or right. Count the paths whose sum of visited elements is divisible by k. The answer can be huge, so return it modulo 10⁹ + 7.

Inputgrid = [[5,2,4],[3,0,5],[0,7,2]], k = 3

Output2

Two paths have a sum divisible by 3: 5+2+4+5+2 = 18 and 5+3+0+5+2 = 15. Both are multiples of 3.

grid (rows separated by ;, values by ,)

def numberOfPaths(grid, k):
    MOD = 10**9 + 7
    m, n = len(grid), len(grid[0])
    # dp[i][j][r] = paths to (i,j) whose sum % k == r
    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):
            if i == 0 and j == 0:
                continue
            v = grid[i][j] % k
            for r in range(k):
                ways = 0
                if i > 0:
                    ways += dp[i - 1][j][r]   # came from above
                if j > 0:
                    ways += dp[i][j - 1][r]   # came from left
                nr = (r + v) % k              # add this cell
                dp[i][j][nr] = (dp[i][j][nr] + ways) % MOD
    return dp[m - 1][n - 1][0]

function numberOfPaths(grid, k) {
  const MOD = 1000000007n;
  const m = grid.length, n = grid[0].length;
  // dp[i][j][r] = paths to (i,j) whose sum % k == r
  const dp = Array.from({ length: m }, () =>
    Array.from({ length: n }, () => new Array(k).fill(0n)));
  dp[0][0][grid[0][0] % k] = 1n;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i === 0 && j === 0) continue;
      const v = grid[i][j] % k;
      for (let r = 0; r < k; r++) {
        let ways = 0n;
        if (i > 0) ways += dp[i - 1][j][r];   // from above
        if (j > 0) ways += dp[i][j - 1][r];   // from left
        const nr = (r + v) % k;               // add this cell
        dp[i][j][nr] = (dp[i][j][nr] + ways) % MOD;
      }
    }
  }
  return Number(dp[m - 1][n - 1][0]);
}

int numberOfPaths(int[][] grid, int k) {
    final int MOD = 1_000_000_007;
    int m = grid.length, n = grid[0].length;
    // dp[i][j][r] = paths to (i,j) whose sum % k == r
    long[][][] dp = new long[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++) {
            if (i == 0 && j == 0) continue;
            int v = grid[i][j] % k;
            for (int r = 0; r < k; r++) {
                long ways = 0;
                if (i > 0) ways += dp[i - 1][j][r];   // from above
                if (j > 0) ways += dp[i][j - 1][r];   // from left
                int nr = (r + v) % k;                 // add this cell
                dp[i][j][nr] = (dp[i][j][nr] + ways) % MOD;
            }
        }
    }
    return (int) dp[m - 1][n - 1][0];
}

int numberOfPaths(vector<vector<int>>& grid, int k) {
    const int MOD = 1e9 + 7;
    int m = grid.size(), n = grid[0].size();
    // dp[i][j][r] = paths to (i,j) whose sum % k == r
    vector<vector<vector<long long>>> dp(m,
        vector<vector<long long>>(n, vector<long long>(k, 0)));
    dp[0][0][grid[0][0] % k] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0) continue;
            int v = grid[i][j] % k;
            for (int r = 0; r < k; r++) {
                long long ways = 0;
                if (i > 0) ways += dp[i - 1][j][r];   // from above
                if (j > 0) ways += dp[i][j - 1][r];   // from left
                int nr = (r + v) % k;                 // add this cell
                dp[i][j][nr] = (dp[i][j][nr] + ways) % MOD;
            }
        }
    }
    return (int) dp[m - 1][n - 1][0];
}

Explanation

This is a classic grid-path dynamic program with one extra twist. Normally we count paths to each cell, but here only the remainder of the running sum modulo k decides whether a path counts. So we carry the remainder as an extra dimension of the state.

The key insight from the hints: the actual numbers do not matter, only grid[i][j] % k. We define dp[i][j][r] = the number of paths from (0,0) to (i,j) whose visited-element sum leaves remainder r when divided by k.

Every cell (except the start) is reached from the cell above or the cell to the left. A path that arrived at a neighbor with remainder r becomes a path at the current cell with remainder (r + grid[i][j]) % k once we step onto it. So for each remainder r we add the neighbors' counts and route them into the bucket nr = (r + v) % k, where v = grid[i][j] % k.

The base case seeds the start cell: dp[0][0][grid[0][0] % k] = 1, one path whose sum is just the first cell. All arithmetic is kept modulo 10⁹ + 7 because the path count can explode.

The answer is dp[m-1][n-1][0] — paths reaching the corner with remainder 0, i.e. a total sum divisible by k. In the example grid with k = 3, exactly 2 of the six possible paths land in bucket 0.

Time: O(m · n · k) Space: O(m · n · k)