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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Paths in Matrix Whose Sum Is Divisible by K

Number: 2521

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an m x n integer matrix grid and an integer k, you need to count the number of paths from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1) by moving only down or right such that the sum of the elements on the path is divisible by k. The final count should be returned modulo 10^9+7.

Key Insights

  • Use dynamic programming to traverse the grid while maintaining the sum modulo k.
  • At every cell, consider paths coming from the top and left; accumulate ways based on current cell value.
  • The state representation is dp[i][j][r] where r represents the remainder (sum % k) of the path reaching (i, j).
  • Since k is relatively small (up to 50) and total grid cells are at most 5 * 10^4, a 3D DP state is feasible.
  • Always take modulo arithmetic (10^9+7) to avoid overflow.

Space and Time Complexity

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

Solution

We solve the problem using a dynamic programming (DP) approach where each cell maintains an array (or vector) of length k. Each index of this array represents the number of ways to reach that cell with a particular sum remainder modulo k.

  1. Initialize dp[0][0][grid[0][0] % k] = 1.
  2. For each cell (i, j), update its DP state by considering contributions from the top (i-1, j) and left (i, j-1). For every remainder from a previous cell, update the current remainder r_new = (previous remainder + grid[i][j]) % k.
  3. Continue processing the grid until the bottom-right cell is reached.
  4. The answer is the value at dp[m-1][n-1][0] since a remainder 0 indicates that the sum is divisible by k.
  5. Take modulo 10^9+7 at each step to manage large numbers.

Code Solutions

MOD = 10**9 + 7

def numberOfPaths(grid, k):
    m, n = len(grid), len(grid[0])
    # Create a 3D dp array with dimensions [m][n][k] initialized to 0
    dp = [[[0] * k for _ in range(n)] for _ in range(m)]
    
    # Setup for the starting cell (0, 0)
    dp[0][0][grid[0][0] % k] = 1
    
    for i in range(m):
        for j in range(n):
            # Skip starting cell since it is already initialized
            if i == 0 and j == 0:
                continue
            for rem in range(k):
                ways = 0
                # If coming from top, add the number of ways from cell (i-1, j)
                if i > 0:
                    ways = (ways + dp[i-1][j][rem]) % MOD
                # If coming from left, add the number of ways from cell (i, j-1)
                if j > 0:
                    ways = (ways + dp[i][j-1][rem]) % MOD
                # The new remainder when current grid value is added
                newRem = (rem + grid[i][j]) % k
                dp[i][j][newRem] = (dp[i][j][newRem] + ways) % MOD
                
    return dp[m-1][n-1][0]

# Example usage:
# grid = [[5,2,4],[3,0,5],[0,7,2]]
# k = 3
# print(numberOfPaths(grid, k))  # Output: 2
← Back to All Questions