Paths in Matrix Whose Sum Is Divisible by K

Paths in Matrix Whose Sum Is Divisible by K - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[5,2,4],[3,0,5],[0,7,2]], k = 3

› Output: 2

💡 Note: There are two paths with sum divisible by 3: Path 1: 5→2→4→5→2 = 18 (18%3=0), Path 2: 5→3→0→7→2 = 17... Actually checking: 5→2→0→7→2=16, 5→3→0→7→2=17. Need to verify paths carefully.

Example 2 — Small Grid

$ Input: grid = [[5,2],[4,3]], k = 2

› Output: 2

💡 Note: Two paths: 5→2→3=10 (10%2=0) and 5→4→3=12 (12%2=0). Both sums are divisible by 2.

Example 3 — No Valid Paths

$ Input: grid = [[1,2],[3,4]], k = 10

› Output: 0

💡 Note: Path 1: 1→2→4=7, Path 2: 1→3→4=8. Neither 7 nor 8 is divisible by 10.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 5 × 10¹
0 ≤ grid[i][j] ≤ 100
1 ≤ k ≤ 50

Visualization

Tap to expand

Understanding the Visualization

Input

Matrix with start at (0,0) and end at (m-1,n-1)

Process

Find all paths moving only right or down

Output

Count paths where sum of elements is divisible by k

Key Takeaway

🎯 Key Insight: Track remainder (sum % k) instead of full sum to efficiently count valid paths

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to use dynamic programming tracking remainder states instead of full sums. Best approach uses 3D DP with state dp[i][j][remainder] representing paths to position (i,j) with sum remainder r. Time: O(m×n×k), Space: O(m×n×k)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(mnk)	O(mnk)	Cache results based on position and sum remainder
3D Dynamic Programming	O(mnk)	O(mnk)	Bottom-up DP with 3D table for optimal solution
Recursive Brute Force	O(2^(m+n))	O(m+n)	Try all possible paths using recursion

Memoized Recursion — Algorithm Steps

Use 3D memoization: memo[i][j][sum%k]
Store computed results to avoid recalculation
Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

State

Track (position, remainder) as unique state

Cache

Store computed results in memo table

Reuse

Return cached result for seen states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAX_STATES 100000

typedef struct {
    int i, j, remainder;
    int result;
} MemoEntry;

MemoEntry memo[MAX_STATES];
int memoSize = 0;

int findMemo(int i, int j, int remainder) {
    for (int idx = 0; idx < memoSize; idx++) {
        if (memo[idx].i == i && memo[idx].j == j && memo[idx].remainder == remainder) {
            return memo[idx].result;
        }
    }
    return -1;
}

void addMemo(int i, int j, int remainder, int result) {
    if (memoSize < MAX_STATES) {
        memo[memoSize].i = i;
        memo[memoSize].j = j;
        memo[memoSize].remainder = remainder;
        memo[memoSize].result = result;
        memoSize++;
    }
}

int dfs(int** grid, int m, int n, int i, int j, int remainder, int k) {
    if (i == m - 1 && j == n - 1) {
        return (remainder + grid[i][j]) % k == 0 ? 1 : 0;
    }
    
    if (i >= m || j >= n) {
        return 0;
    }
    
    int cached = findMemo(i, j, remainder);
    if (cached != -1) {
        return cached;
    }
    
    int paths = 0;
    int newRemainder = (remainder + grid[i][j]) % k;
    
    // Move right
    if (j + 1 < n) {
        paths = (paths + dfs(grid, m, n, i, j + 1, newRemainder, k)) % MOD;
    }
    
    // Move down
    if (i + 1 < m) {
        paths = (paths + dfs(grid, m, n, i + 1, j, newRemainder, k)) % MOD;
    }
    
    addMemo(i, j, remainder, paths);
    return paths;
}

int solution(int** grid, int m, int n, int k) {
    memoSize = 0;
    return dfs(grid, m, n, 0, 0, 0, k);
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int k;
    scanf("%d", &k);
    
    int** grid = malloc(10 * sizeof(int*));
    for (int i = 0; i < 10; i++) {
        grid[i] = malloc(10 * sizeof(int));
    }
    
    int m = 2, n = 2;
    grid[0][0] = 5; grid[0][1] = 2;
    grid[1][0] = 4; grid[1][1] = 3;
    
    printf("%d\n", solution(grid, m, n, k));
    
    for (int i = 0; i < 10; i++) {
        free(grid[i]);
    }
    free(grid);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m*n*k)

Each state (i,j,remainder) computed once, m*n positions with k possible remainders

✓ Linear Growth

Space Complexity

O(m*n*k)

3D memoization table plus recursion stack depth O(m+n)

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler