Paths in Matrix Whose Sum Is Divisible by K — Solution
Paths in Matrix Whose Sum Is Divisible by K solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Paths in Matrix Whose Sum Is Divisible by K is a hard coding problem on arrays, dynamic programming and matrix, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Matrix
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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.lengthn == grid[i].length1 <= m, n <= 5 * 10^41 <= m * n <= 5 * 10^40 <= grid[i][j] <= 1001 <= k <= 50
Hints for Paths in Matrix Whose Sum Is Divisible by K
Hint 1
You cannot enumerate paths — there are exponentially many. Count them by the remainder they carry.
Hint 2
dp[i][j][r]= the number of paths reaching(i, j)whose partial sum isrmodulok.Hint 3
A path arriving with remainder
rat(i, j)came from a neighbour with remainder(r - grid[i][j]) mod k.
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
- Initialise
dp[0][0][grid[0][0] mod k] = 1. - 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. - Sum the contributions from above and from the left, modulo 10⁹ + 7.
- 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 = 1makes 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]Java
public static int numberOfPaths(int[][] grid, int k) {
final int MOD = 1000000007;
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++) {
if (i == 0 && j == 0) continue;
int v = grid[i][j] % k;
for (int r = 0; r < k; r++) {
int prev = ((r - v) % k + k) % k;
long total = 0;
if (i > 0) total += dp[i - 1][j][prev];
if (j > 0) total += dp[i][j - 1][prev];
dp[i][j][r] = (int) (total % MOD);
}
}
}
return dp[m - 1][n - 1][0];
}C++
int numberOfPaths(vector<vector<int>>& grid, int k) {
const int MOD = 1000000007;
int m = (int) grid.size(), n = (int) grid[0].size();
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(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++) {
int prev = ((r - v) % k + k) % k;
long long total = 0;
if (i > 0) total += dp[i - 1][j][prev];
if (j > 0) total += dp[i][j - 1][prev];
dp[i][j][r] = (int) (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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming