Paths in Matrix Whose Sum Is Divisible by K
01 · Problem
You are given an m x n grid of non-negative integers and a positive integer k. Starting at the top-left cell (0, 0) you may only move right or down, and you must end at the bottom-right cell (m - 1, n - 1).
Return the number of such paths where the sum of all visited cells (including the start and end cells) is divisible by k. Return the count modulo 10^9 + 7.
02 · Examples
grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3
2
Two paths have a sum divisible by 3: 5 -> 2 -> 4 -> 5 -> 2 with sum 18, and 5 -> 3 -> 0 -> 5 -> 2 with sum 15.
grid = [[0,0]], k = 5
1
The only path visits both cells and has sum 0, which is divisible by 5.
grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1
10
Every sum is divisible by 1, so all 10 right/down paths in a 3 x 4 grid count.
03 · Constraints
- 01m == grid.length, n == grid[i].length
- 021 <= m, n <= 5 * 104 and 1 <= m * n <= 5 * 104
- 030 <= grid[i][j] <= 100
- 041 <= k <= 50
04 · Optimal complexity
- Time
- O(m * n * k)
- Space
- O(m * n * k)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.