Count paths whose sum is not divisible by K in given Matrix

0 0 10 minutes read

Given an integer matrix mat[][] of size M x N and an integer K, the task is to return the number of paths from top-left to bottom-right by moving only right and downwards such that the sum of the elements on the path is not divisible by K.

Examples:

Input: mat = [[5, 2, 4], [3, 0, 5], [0, 7, 2]], K = 3
Output: 4

Input: mat = [[0], [0]], K = 7
Output: 0

Approach: The problem can be solved using recursion based on the following idea:

Step 1:

When we have reached the destination, check if the sum is not divisible by K, then we return 1.

When we have crossed the boundary of the matrix and we couldn’t find the right path, hence we return 0.

Step 2: Try out all possible choices at a given index:

At every index we have two choices, one to go down and the other to go right. To go down, increase i by 1, and to move towards the right increase j by 1.

Step 3: Count all ways:

As we have to count all the possible unique paths, return the sum of all the choices (down and right) from each recursion.

Follow the steps mentioned below to implement the idea:

Create a recursive function.
For each call, there are two choices for the element as mentioned above.
Calculate the value of all possible cases as mentioned above.
The sum of all choices is the required answer.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for calculating paths
int solve(int i, int j, int local_sum,
          vector<vector<int> >& grid, int k, int m, int n)
{
    // Base case
    if (i > m - 1 || j > n - 1)
        return 0;
    if (i == m - 1 && j == n - 1) {
        if ((local_sum + grid[i][j]) % k != 0)
            return 1;
        else
            return 0;
    }
 
    // Choices of exploring paths
    int right = solve(i, j + 1, (local_sum + grid[i][j]),
                      grid, k, m, n);
    int down = solve(i + 1, j, (local_sum + grid[i][j]),
                     grid, k, m, n);
 
    // Returning the sum of the choices
    return (right + down);
}
 
// Driver code
int main()
{
    vector<vector<int> > mat
        = { { 5, 2, 4 }, { 3, 0, 5 }, { 0, 7, 2 } };
    int K = 3;
 
    int M = mat.size();
    int N = mat[0].size();
 
    // Function call
    int ways = solve(0, 0, 0, mat, K, M, N);
    cout << ways << endl;
    return 0;
}

Java

// java code to implement the approach
import java.util.Scanner; 
import java.io.*;
 
class GFG
{
   
// Function for calculating paths
public static int solve(int i, int j, int local_sum,
         int[][] grid, int k, int m, int n)
{
    // Base case
    if (i > m - 1 || j > n - 1)
        return 0;
    if (i == m - 1 && j == n - 1) {
        if ((local_sum + grid[i][j]) % k != 0)
            return 1;
        else
            return 0;
    }
 
    // Choices of exploring paths
    int right = solve(i, j + 1, (local_sum + grid[i][j]),
                      grid, k, m, n);
    int down = solve(i + 1, j, (local_sum + grid[i][j]),
                     grid, k, m, n);
 
    // Returning the sum of the choices
    return (right + down);
}
 
// Driver code
 public static void main(String[] args)
 {
    
       // System.out.println("Hello, World!");
    int [][]mat
        = { { 5, 2, 4 }, { 3, 0, 5 }, { 0, 7, 2 } };
    int K = 3;
 
    int M = mat.length;
    int N = mat[0].length;
 
    // Function call
    int ways = solve(0, 0, 0, mat, K, M, N);
    System.out.println(ways);
     }
}
 
// this code is contributed by ksam24000

Python3

# Python code to implement the approach
 
# Function for calculating paths
def solve(i, j, local_sum, grid, k, m, n):
 
    # Base case
    if (i > m - 1 or j > n - 1):
        return 0
    if (i == m - 1 and j == n - 1):
        if ((local_sum + grid[i][j]) % k != 0):
            return 1
        else:
            return 0
 
    # Choices of exploring paths
    right = solve(i, j + 1, (local_sum + grid[i][j]),
                  grid, k, m, n)
    down = solve(i + 1, j, (local_sum + grid[i][j]),
                 grid, k, m, n)
 
    # Returning the sum of the choices
    return (right + down)
 
# Driver code
mat = [[5, 2, 4], [3, 0, 5], [0, 7, 2]]
K = 3
 
M = len(mat)
N = len(mat[0])
 
# Function call
ways = solve(0, 0, 0, mat, K, M, N)
print(ways)
 
# This code is contributed by Saurabh Jaiswal

C#

// C# code to implement the above approach
using System;
public class GFG
{
 
  // Function for calculating paths
  public static int solve(int i, int j, int local_sum,
                          int[,] grid, int k, int m, int n)
  {
 
    // Base case
    if (i > m - 1 || j > n - 1)
      return 0;
    if (i == m - 1 && j == n - 1) {
      if ((local_sum + grid[i,j]) % k != 0)
        return 1;
      else
        return 0;
    }
 
    // Choices of exploring paths
    int right = solve(i, j + 1, (local_sum + grid[i,j]),
                      grid, k, m, n);
    int down = solve(i + 1, j, (local_sum + grid[i,j]),
                     grid, k, m, n);
 
    // Returning the sum of the choices
    return (right + down);
  }
 
  // Driver code
  public static void Main(string[] args)
  {
 
    // System.out.println("Hello, World!");
    int [,] mat = { { 5, 2, 4 }, { 3, 0, 5 }, { 0, 7, 2 } };
    int K = 3;
 
    int M = mat.GetLength(0);
    int N = mat.GetLength(1);
 
    // Function call
    int ways = solve(0, 0, 0, mat, K, M, N);
    Console.WriteLine(ways);
  }
}
 
// This code is contributed by AnkThon

Javascript

<script>
    // JavaScript code to implement the approach
 
    // Function for calculating paths
    const solve = (i, j, local_sum, grid, k, m, n) => {
     
        // Base case
        if (i > m - 1 || j > n - 1)
            return 0;
        if (i == m - 1 && j == n - 1) {
            if ((local_sum + grid[i][j]) % k != 0)
                return 1;
            else
                return 0;
        }
 
        // Choices of exploring paths
        let right = solve(i, j + 1, (local_sum + grid[i][j]),
            grid, k, m, n);
        let down = solve(i + 1, j, (local_sum + grid[i][j]),
            grid, k, m, n);
 
        // Returning the sum of the choices
        return (right + down);
    }
 
    // Driver code
    let mat
        = [[5, 2, 4], [3, 0, 5], [0, 7, 2]];
    let K = 3;
 
    let M = mat.length;
    let N = mat[0].length;
 
    // Function call
    let ways = solve(0, 0, 0, mat, K, M, N);
    document.write(ways)
 
// This code is contributed by rakeshsahni
 
</script>

Output

Time Complexity: O(^(M+N-2)C_(M-1)) as there can be this many paths
Auxiliary Space: O(N + M) recursion stack space as the path length is (M-1) + (N-1)

Efficient Approach (Using Memoization):

We can use Dynamic Programming to store the answer for overlapping subproblems. We can store the result for the current index i and j and the sum in the DP matrix.

The states of DP can be represented as follows:

DP[i][j][local_sum]

Below is the implementation of the above approach:

C++

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function for calculating paths
int solve(int i, int j, int local_sum,
          vector<vector<int> >& grid, int k, int m, int n, vector<vector<vector<int>>> &dp)
{
    // Base case
    if (i > m - 1 || j > n - 1)
        return 0;
    if (i == m - 1 && j == n - 1) {
        if ((local_sum + grid[i][j]) % k != 0)
            return 1;
        else
            return 0;
    }
     
    // If answer already stored return that
    if(dp[i][j][local_sum] != -1) return dp[i][j][local_sum];
 
    // Choices of exploring paths
    int right = solve(i, j + 1, (local_sum + grid[i][j]) % k,
                      grid, k, m, n, dp);
    int down = solve(i + 1, j, (local_sum + grid[i][j]) % k,
                     grid, k, m, n, dp);
 
    // Returning the sum of the choices
    return dp[i][j][local_sum] = (right + down);
}
 
// Driver code
int main()
{
    vector<vector<int> > mat
        = { { 5, 2, 4 }, { 3, 0, 5 }, { 0, 7, 2 } };
    int K = 3;
 
    int M = mat.size();
    int N = mat[0].size();
     
     // 3d dp vector
    vector<vector<vector<int>>> dp(M, vector<vector<int>>(N, vector<int>(K,-1)));
 
    // Function call
    int ways = solve(0, 0, 0, mat, K, M, N, dp);
    cout << ways << endl;
    return 0;
}

Java

// Java code to implement the approach
import java.util.*;
 
public class GFG {
 
  // Function for calculating paths
  static int solve(int i, int j, int local_sum,
                   int[][] grid, int k, int m, int n,
                   int[][][] dp)
  {
     
    // Base case
    if (i > m - 1 || j > n - 1)
      return 0;
    if (i == m - 1 && j == n - 1) {
      if ((local_sum + grid[i][j]) % k != 0)
        return 1;
      else
        return 0;
    }
 
    // If answer already stored return that
    if (dp[i][j][local_sum] != -1)
      return dp[i][j][local_sum];
 
    // Choices of exploring paths
    int right
      = solve(i, j + 1, (local_sum + grid[i][j]) % k,
              grid, k, m, n, dp);
    int down
      = solve(i + 1, j, (local_sum + grid[i][j]) % k,
              grid, k, m, n, dp);
 
    // Returning the sum of the choices
    return dp[i][j][local_sum] = (right + down);
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int[][] mat
      = { { 5, 2, 4 }, { 3, 0, 5 }, { 0, 7, 2 } };
    int K = 3;
 
    int M = mat.length;
    int N = mat[0].length;
 
    // 3d dp vector
    int[][][] dp
      = new int[M][N][K]; //(M, vector<vector<int>>(N,
    // vector<int>(K,-1)));
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        for (int k = 0; k < K; k++) {
          dp[i][j][k] = -1;
        }
      }
    }
 
    // Function call
    int ways = solve(0, 0, 0, mat, K, M, N, dp);
    System.out.println(ways);
  }
}
 
// This code is contributed by Karandeep1234

Python3

def solve(i, j, local_sum, grid, k, m, n, dp):
    # Base case
    if i > m - 1 or j > n - 1:
        return 0
    if i == m - 1 and j == n - 1:
        if (local_sum + grid[i][j]) % k != 0:
            return 1
        else:
            return 0
    # If answer already stored return that
    if dp[i][j][local_sum] != -1:
        return dp[i][j][local_sum]
 
    # Choices of exploring paths
    right = solve(i, j + 1, (local_sum + grid[i][j]) % k, grid, k, m, n, dp)
    down = solve(i + 1, j, (local_sum + grid[i][j]) % k, grid, k, m, n, dp)
 
    # Returning the sum of the choices
    dp[i][j][local_sum] = (right + down)
    return dp[i][j][local_sum]
 
# Driver code
if __name__ == "__main__":
    mat = [[5, 2, 4], [3, 0, 5], [0, 7, 2]]
    K = 3
    M = len(mat)
    N = len(mat[0])
 
    # 3d dp list
    dp = [[[-1 for k in range(K)] for j in range(N)] for i in range(M)]
 
    # Function call
    ways = solve(0, 0, 0, mat, K, M, N, dp)
    print(ways)
 
# This code is contributed by Vikram_Shirsat

C#

using System;
 
class GFG {
  // Function for calculating paths
  static int Solve(int i, int j, int localSum,
                   int[,] grid, int k, int m, int n,
                   int[,,] dp)
  {
    // Base case
    if (i > m - 1 || j > n - 1)
      return 0;
    if (i == m - 1 && j == n - 1) {
      if ((localSum + grid[i, j]) % k != 0)
        return 1;
      else
        return 0;
    }
 
    // If answer already stored return that
    if (dp[i, j, localSum] != -1)
      return dp[i, j, localSum];
 
    // Choices of exploring paths
    int right
      = Solve(i, j + 1, (localSum + grid[i, j]) % k,
              grid, k, m, n, dp);
    int down
      = Solve(i + 1, j, (localSum + grid[i, j]) % k,
              grid, k, m, n, dp);
 
    // Returning the sum of the choices
    return dp[i, j, localSum] = (right + down);
  }
 
  // Driver code
  static void Main(string[] args)
  {
    int[,] mat
      = {{5, 2, 4}, {3, 0, 5}, {0, 7, 2}};
    int K = 3;
 
    int M = mat.GetLength(0);
    int N = mat.GetLength(1);
 
    // 3d dp array
    int[,,] dp
      = new int[M, N, K];
    for (int i = 0; i < M; i++) {
      for (int j = 0; j < N; j++) {
        for (int k = 0; k < K; k++) {
          dp[i, j, k] = -1;
        }
      }
    }
 
    // Function call
    int ways = Solve(0, 0, 0, mat, K, M, N, dp);
    Console.WriteLine(ways);
  }
}

Javascript

// Javascript code to implement the approach
function solve(i, j, local_sum, grid, k, m, n, dp){
// Base case
if (i > m - 1 || j > n - 1){
return 0;
}
if (i == m - 1 && j == n - 1){
if ((local_sum + grid[i][j]) % k !== 0){
return 1;
}
else{
return 0;
}
}
// If answer already stored return that
if (dp[i][j][local_sum] !== -1){
return dp[i][j][local_sum];
}
// Choices of exploring paths
let right = solve(i, j + 1, (local_sum + grid[i][j]) % k, grid, k, m, n, dp);
let down = solve(i + 1, j, (local_sum + grid[i][j]) % k, grid, k, m, n, dp);
 
// Returning the sum of the choices
dp[i][j][local_sum] = (right + down);
return dp[i][j][local_sum];
}
 
// Driver code
let mat = [[5, 2, 4], [3, 0, 5], [0, 7, 2]];
let K = 3;
let M = mat.length;
let N = mat[0].length;
 
// 3d dp list
let dp = new Array(M);
for(let i=0;i<M;i++){
dp[i] = new Array(N);
for(let j=0;j<N;j++){
dp[i][j] = new Array(K).fill(-1);
}
}
 
// Function call
let ways = solve(0, 0, 0, mat, K, M, N, dp);
console.log(ways);
 
//This code is contributed by shivamsharma215

Output

Time Complexity: O(m*n*k), where len is the length of the array
Auxiliary Space: O(m*n*k)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!