You are given a 0-indexed m x n integer matrix grid and an integer k. You are currently at position (0, 0) and you want to reach position (m - 1, n - 1) moving only down or right.
Return the number of paths where the sum of the elements on the path is divisible by k. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3 Output: 2 Explanation: There are two paths where the sum of the elements on the path is divisible by k. The first path highlighted in red has a sum of 5 + 2 + 4 + 5 + 2 = 18 which is divisible by 3. The second path highlighted in blue has a sum of 5 + 3 + 0 + 5 + 2 = 15 which is divisible by 3.
Example 2:
Input: grid = [[0,0]], k = 5 Output: 1 Explanation: The path highlighted in red has a sum of 0 + 0 = 0 which is divisible by 5.
Example 3:
Input: grid = [[7,3,4,9],[2,3,6,2],[2,3,7,0]], k = 1 Output: 10 Explanation: Every integer is divisible by 1 so the sum of the elements on every possible path is divisible by k.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 5 * 1041 <= m * n <= 5 * 1040 <= grid[i][j] <= 1001 <= k <= 50We can use dynamic programming to solve this problem by maintaining a 3D array dp where dp[i][j][mod] keeps track of the number of paths to reach the position (i, j) with a sum that when divided by k leaves a remainder mod.
Our transition will involve checking paths from the top and left cells, updating the path count for each new modulo state by adding the current cell's value.
Start by initializing dp[0][0][grid[0][0] % k] = 1 since starting at the grid's top-left corner with the initial sum modulo.
This C implementation initializes a 3D DP array to store the path counts with specific modulo sums.
Iterate over the grid, updating the DP state based on transitions from the top and left cells. The end result is found in dp[m-1][n-1][0].
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n * k) since we traverse the whole matrix for each modulo state.
Space Complexity: O(m * n * k) for the 3D DP array.
Subarray Sums Divisible by K - Leetcode 974 - Python • NeetCodeIO • 23,675 views views
Watch 9 more video solutions →Practice Paths in Matrix Whose Sum Is Divisible by K with our built-in code editor and test cases.
Practice on FleetCode