The Paths in Matrix Whose Sum Is Divisible by K problem asks you to count all paths from the top-left to bottom-right of a grid (moving only right or down) where the path sum is divisible by k. This hard coding problem uses DP with modular arithmetic as an extra dimension. The array, matrix, and dynamic programming interview pattern with modular state tracking is the core.
Google asks this because it extends standard grid path counting with a divisibility constraint. The key insight: instead of tracking exact sums (too large), track sum mod k as the DP state. The array, matrix, and dynamic programming interview pattern is demonstrated with this elegant state reduction.
3D DP with modular state. dp[i][j][r] = number of paths to cell (i,j) with sum ≡ r (mod k). Transition: dp[i][j][(r + grid[i][j]) % k] += dp[i-1][j][r] + dp[i][j-1][r]. Initialize: dp[0][0][grid[0][0] % k] = 1. Answer: dp[m-1][n-1][0].
Grid=[[5,2],[4,3]], k=3. Paths: (0,0)→(0,1)→(1,1): 5+2+3=10. 10%3≠0. (0,0)→(1,0)→(1,1): 5+4+3=12. 12%3=0 ✓. Count = 1.
DP: dp[0][0][5%3=2]=1. dp[0][1][2+2%3=1]=1. dp[1][0][2+4%3=2+1=0]=1. dp[1][1]: from dp[0][1][1] with +3%3=0: r=1+0=1→count=1. From dp[1][0][0] with +3%3=0: r=0→count=1. dp[1][1][1]+=1, dp[1][1][0]+=1. Answer=dp[1][1][0]=1 ✓.
Grid path counting with divisibility constraints always uses sum mod k as an extra DP state. This reduces the state space from O(mn * max_sum) to O(mn * k). Practice this approach on: "number of paths with sum divisible by k in an array" (1D version), then extend to 2D grids. The modular DP pattern generalizes to any "count paths satisfying a divisibility property."
| Title | Difficulty | Topics | LeetCode |
|---|---|---|---|
| Check if There Is a Valid Parentheses String Path | Hard | Solve | |
| Count Fertile Pyramids in a Land | Hard | Solve | |
| Maximum Vacation Days | Hard | Solve | |
| Minimum Falling Path Sum II | Hard | Solve | |
| Cherry Pickup II | Hard | Solve |
