Get started

Paths in Matrix Whose Sum Is Divisible by K — Hard Problem & Solution

Starting at the top-left cell and moving only right or down, reach the bottom-right cell.

Problem statement

Starting at the top-left cell and moving only right or down, reach the bottom-right cell. A path's value is the sum of the cells it visits, start and end included.

Return the number of paths whose value is divisible by k, modulo 10⁹ + 7.

Example 1

Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
Output: 2
Explanation: Two of the six paths sum to a multiple of 3.

Example 2

Input: grid = [[0,0]], k = 5
Output: 1
Explanation: The single path sums to 0, which is divisible by anything.

Example 3

Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
Output: 10
Explanation: Every sum is divisible by 1, so all ten paths count.

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

How to solve Paths in Matrix Whose Sum Is Divisible by K

Add the remainder to the DP state. dp[i][j][r] counts the paths to (i, j) whose sum leaves remainder r. Each cell pulls from the cell above and the cell to the left, shifting the remainder back by the cell's own value.

Approach

  1. Initialise dp[0][0][grid[0][0] mod k] = 1.
  2. Sweep in row-major order. For each cell and each target remainder r, the contributing remainder upstream is ((r - grid[i][j]) mod k + k) mod k.
  3. Sum the contributions from above and from the left, modulo 10⁹ + 7.
  4. Return dp[m-1][n-1][0].

Why it works

Remainders are the only thing about a partial sum that can still matter, so folding the sum into k buckets is lossless and turns an exponential path count into O(m · n · k) states. The double modulo on r - grid[i][j] is not decoration: in most languages the % of a negative number is negative, which would index out of the array.

Complexity

  • Time — O(m · n · k)
  • Space — O(m · n · k), reducible to O(n · k) with a rolling row

Pitfalls

  • A negative intermediate remainder must be normalised before it indexes the table.
  • The starting cell's own value counts towards the sum.
  • k = 1 makes every path count — a useful sanity check on the indexing.

Reference solution

Python

from typing import List

def numberOfPaths(grid: List[List[int]], k: int) -> int:
    MOD = 10**9 + 7
    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
    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):
                prev = (r - v) % k
                total = 0
                if i > 0:
                    total += dp[i - 1][j][prev]
                if j > 0:
                    total += dp[i][j - 1][prev]
                dp[i][j][r] = total % MOD
    return dp[m - 1][n - 1][0]

JavaScript

var numberOfPaths = function(grid, k) {
    var MOD = 1000000007;
    var m = grid.length, n = grid[0].length, i, j, r;
    var dp = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) {
            var cell = [];
            for (r = 0; r < k; r++) cell.push(0);
            row.push(cell);
        }
        dp.push(row);
    }
    dp[0][0][grid[0][0] % k] = 1;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            if (i === 0 && j === 0) continue;
            var v = grid[i][j] % k;
            for (r = 0; r < k; r++) {
                var prev = ((r - v) % k + k) % k;
                var total = 0;
                if (i > 0) total += dp[i - 1][j][prev];
                if (j > 0) total += dp[i][j - 1][prev];
                dp[i][j][r] = total % MOD;
            }
        }
    }
    return dp[m - 1][n - 1][0];
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue