We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Paths in Matrix Whose Sum Is Divisible by K

Difficulty: Hard

Problem Description

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^9 + 7.

Key Insights

  • You can only move down or right, leading to a constrained path exploration.
  • The sum of the elements along the path must be evaluated for divisibility by k.
  • Dynamic programming can be utilized to keep track of the number of paths leading to each cell with respect to the modulo k of their sum.
  • The problem requires efficient handling of potentially large inputs due to the constraints.

Space and Time Complexity

Time Complexity: O(m * n * k)
Space Complexity: O(n * k)

Solution

The solution employs a dynamic programming approach where we maintain a 2D array dp[i][j][r] that represents the number of ways to reach cell (i, j) with a sum of elements modulo k equal to r. The algorithm iterates through the grid, updating the number of paths for each cell based on the possible movements from the left and above cells. The result is found by summing all paths leading to the bottom-right cell (m-1, n-1) that have sums divisible by k.

Code Solutions

def countPaths(grid, k):
    MOD = 10**9 + 7
    m, n = len(grid), len(grid[0])
    
    dp = [[[0] * k for _ in range(n)] for __ in range(m)]
    dp[0][0][grid[0][0] % k] = 1
    
    for i in range(m):
        for j in range(n):
            for r in range(k):
                if dp[i][j][r] > 0:
                    if i + 1 < m:  # Move down
                        new_r = (r + grid[i + 1][j]) % k
                        dp[i + 1][j][new_r] = (dp[i + 1][j][new_r] + dp[i][j][r]) % MOD
                    if j + 1 < n:  # Move right
                        new_r = (r + grid[i][j + 1]) % k
                        dp[i][j + 1][new_r] = (dp[i][j + 1][new_r] + dp[i][j][r]) % MOD
    
    return dp[m - 1][n - 1][0]
← Back to All Questions