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: 4Input: 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 pathsint 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 codeint 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 approachimport java.util.Scanner; import java.io.*;class GFG{ // Function for calculating pathspublic 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 pathsdef 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 codemat = [[5, 2, 4], [3, 0, 5], [0, 7, 2]]K = 3M = len(mat)N = len(mat[0])# Function callways = solve(0, 0, 0, mat, K, M, N)print(ways)# This code is contributed by Saurabh Jaiswal |
C#
// C# code to implement the above approachusing 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
4
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 pathsint 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 codeint 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 approachimport 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 codeif __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 approachfunction solve(i, j, local_sum, grid, k, m, n, dp){// Base caseif (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 thatif (dp[i][j][local_sum] !== -1){return dp[i][j][local_sum];}// Choices of exploring pathslet 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 choicesdp[i][j][local_sum] = (right + down);return dp[i][j][local_sum];}// Driver codelet mat = [[5, 2, 4], [3, 0, 5], [0, 7, 2]];let K = 3;let M = mat.length;let N = mat[0].length;// 3d dp listlet 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 calllet ways = solve(0, 0, 0, mat, K, M, N, dp);console.log(ways);//This code is contributed by shivamsharma215 |
Output
4
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
