2435. Paths in Matrix Whose Sum Is Divisible by K

[mah-shamim]

Topics: Array, Dynamic Programming, Matrix, Weekly Contest 314

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 10⁹ + 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.length
• n == grid[i].length
• 1 <= m, n <= 5 * 10⁴
• 1 <= m * n <= 5 * 10⁴
• 0 <= grid[i][j] <= 100
• 1 <= k <= 50

Hint:

1. The actual numbers in grid do not matter. What matters are the remainders you get when you divide the numbers by k.
2. We can use dynamic programming to solve this problem. What can we use as states?
3. Let dp[i][j][value] represent the number of paths where the sum of the elements on the path has a remainder of value when divided by k.

[mah-shamim]

We need to find the number of paths from top-left to bottom-right in a matrix where the sum of elements along the path is divisible by k, moving only right or down.

Approach:

Problem Analysis

• We can only move right or down
• We need to track the sum modulo k for each path
• The constraints are large (up to 50,000 cells) but k is small (≤ 50)

Dynamic Programming Approach

I'll use a 2D DP array where dp[j][r] represents the number of paths to current column j with remainder r.

Since we process row by row, I can optimize space by only storing the current and previous row information.

Let's implement this solution in PHP: 2435. Paths in Matrix Whose Sum Is Divisible by K

<?php
/**
 * @param Integer[][] $grid
 * @param Integer $k
 * @return Integer
 */
function numberOfPaths($grid, $k) {
    $MOD = 1000000007;
    $m = count($grid);
    $n = count($grid[0]);

    // 3D DP: dp[i][j][r] = paths to (i,j) with remainder r
    $dp = array_fill(0, $m, array_fill(0, $n, array_fill(0, $k, 0)));

    // Initialize starting cell
    $firstRem = $grid[0][0] % $k;
    $dp[0][0][$firstRem] = 1;

    for ($i = 0; $i < $m; $i++) {
        for ($j = 0; $j < $n; $j++) {
            $currentVal = $grid[$i][$j] % $k;

            // Skip reprocessing the start cell
            if ($i == 0 && $j == 0) continue;

            // Check paths from top
            if ($i > 0) {
                for ($r = 0; $r < $k; $r++) {
                    if ($dp[$i-1][$j][$r] > 0) {
                        $newRem = ($r + $currentVal) % $k;
                        $dp[$i][$j][$newRem] = ($dp[$i][$j][$newRem] + $dp[$i-1][$j][$r]) % $MOD;
                    }
                }
            }

            // Check paths from left
            if ($j > 0) {
                for ($r = 0; $r < $k; $r++) {
                    if ($dp[$i][$j-1][$r] > 0) {
                        $newRem = ($r + $currentVal) % $k;
                        $dp[$i][$j][$newRem] = ($dp[$i][$j][$newRem] + $dp[$i][$j-1][$r]) % $MOD;
                    }
                }
            }
        }
    }

    return $dp[$m-1][$n-1][0];
}

// Test cases
echo numberOfPaths([[5,2,4],[3,0,5],[0,7,2]], 3) . "\n";        // Output: 2
echo numberOfPaths([[0,0]], 5) . "\n";                          // Output: 1
echo numberOfPaths([[7,3,4,9],[2,3,6,2],[2,3,7,0]], 1) . "\n";  // Output: 10
?>

Explanation:

1. State Definition: dp[i][j][r] = number of paths to cell (i,j) where the sum of elements has remainder r when divided by k

2. Transition:

   • From top: dp[i][j][(r + grid[i][j]) % k] += dp[i-1][j][r]
   • From left: dp[i][j][(r + grid[i][j]) % k] += dp[i][j-1][r]

3. Initialization: Start at (0,0) with remainder grid[0][0] % k

4. Answer: dp[m-1][n-1][0] (paths to bottom-right with remainder 0)

Complexity Analysis

• Time Complexity: O(m × n × k)
• Space Complexity: O(n × k) for optimized version, O(m × n × k) for readable version

[kovatz]

Thanks for solving the problem of "Paths in Matrix Whose Sum Is Divisible by K"

[mah-shamim]

Thanks