224. Paths in Matrix Whose Sum Is Divisible by K
Hard•
Move from the top-left to the bottom-right of grid using only right or down steps. Include the value of every visited cell, including both endpoints, in the path sum.
Return the number of paths whose sum is divisible by k. Different sequences of visited cells count separately. Return the count modulo 1000000007 and do not modify grid. A sum of zero is divisible by every positive k.
Example 1:
Input: grid = [[1,2,3],[4,5,6],[7,8,9]], k = 5
Output: 2
Explanation: Exactly two routes have sums divisible by 5: 1 + 2 + 5 + 8 + 9 = 25 and 1 + 4 + 5 + 6 + 9 = 25. They are different routes even though their sums are equal, so both count.
Example 2:
Input: grid = [[1,1],[1,1]], k = 2
Output: 0
Explanation: Every route visits three cells of value 1, giving sum 3. Neither of the two routes is divisible by 2, so the answer is 0.
Example 3:
Input: grid = [[3,0,3],[0,3,0]], k = 3
Output: 3
Explanation: Every cell value is divisible by 3, so all three routes qualify. A route needs one down and two right moves, and the down move can occupy any of the three positions.
Constraints
- 1 <= rows * cols <= 50000
- 0 <= grid[row][col] <= 100
- 1 <= k <= 50
Accepted3/4|Acceptance Rate75.0%