Given a m x n matrix of positive integers. The task is to find the number of paths from the top left of the matrix to the bottom right of the matrix such that each integer in the path is prime.
Also, print the lexicographical largest path among all the path. A cell (a, b) is lexicographical larger than cell (c, d) either a > b or if a == b then b > d. From cell (x, y), you are allowed to move (x + 1, y), (x, y + 1), (x + 1, y + 1).
Note: It is given that the top-left cell will always have a prime number.
Examples:
Input: n = 3, m = 3
m[][] = { { 2, 3, 7 },
{ 5, 4, 2 },
{ 3, 7, 11 } }Output:
Number of paths: 4
Lexicographical largest path: (1, 1) -> (2, 1) -> (3, 2) -> (3, 3)
There are four ways to reach (3, 3) from (1, 1).
Path 1: (1, 1) (1, 2) (1, 3) (2, 3) (3, 3)
Path 2: (1, 1) (1, 2) (2, 3) (3, 3)
Path 3: (1, 1) (2, 1) (3, 1) (3, 2) (3, 3)
Path 4: (1, 1) (2, 1) (3, 2) (3, 3)
Lexicographical Order -> 4 > 3 > 2 > 1
Approach:
The idea is to use Dynamic Programming to solve the problem. First, observe, a non-prime number in the matrix can be treated as an obstacle and a prime number can be treated as a cell that can be used in the path. So, we can use a sieve to identify the obstacle and convert the given matrix into a binary matrix where 0 indicates the obstacle and 1 indicates the valid path.
So, we will define a 2D matrix, say dp[][], where d[i][j] indicate the number of path from cell (1, 1) to cell(i, j). Also, we can define dp[i][j] as,
dp[i][j] = dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1]
i.e sum of path from left cell, right cell and upper left diagonal (moves allowed).
To find the lexicographical largest path, we can use DFS (Depth-first search). Consider each cell as a node which is having three outgoing edges, one to the cell adjacent right, cell adjacent down, and cell diagonal to lower left. Now, we will travel using a depth-first search in a manner so that we get the lexicographical largest path. So, to get the lexicographical largest path, from the cell (x, y) we first try to travel to cell (x + 1, y + 1) (if no path possible from that cell) then try travel to cell (x + 1, y) and finally to (x, y + 1).
Below is the implementation of this approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;#define MAX 105void sieve(int prime[]){ for (int i = 2; i * i <= MAX; i++) { if (prime[i] == 0) { for (int j = i * i; j <= MAX; j += i) prime[j] = 1; } }}// Depth First Searchvoid dfs(int i, int j, int k, int* q, int n, int m, int mappedMatrix[][MAX], int mark[][MAX], pair<int, int> ans[]){ // Return if cell contain non prime number or obstacle, // or going out of matrix or already visited the cell // or already found the lexicographical largest path if (mappedMatrix[i][j] == 0 || i > n || j > m || mark[i][j] || (*q)) return; // marking cell is already visited mark[i][j] = 1; // storing the lexicographical largest path index ans[k] = make_pair(i, j); // if reached the end of the matrix if (i == n && j == m) { // updating the final number of // steps in lexicographical largest path (*q) = k; return; } // moving diagonal (trying lexicographical largest path) dfs(i + 1, j + 1, k + 1, q, n, m, mappedMatrix, mark, ans); // moving cell right to current cell dfs(i + 1, j, k + 1, q, n, m, mappedMatrix, mark, ans); // moving cell down to current cell. dfs(i, j + 1, k + 1, q, n, m, mappedMatrix, mark, ans);}// Print lexicographical largest prime pathvoid lexicographicalPath(int n, int m, int mappedMatrix[][MAX]){ // to count the number of step in // lexicographical largest prime path int q = 0; // to store the lexicographical // largest prime path index pair<int, int> ans[MAX]; // to mark if the cell is already traversed or not int mark[MAX][MAX]; // traversing by DFS dfs(1, 1, 1, &q, n, m, mappedMatrix, mark, ans); // printing the lexicographical largest prime path for (int i = 1; i <= q; i++) cout << ans[i].first << " " << ans[i].second << "\n";}// Return the number of prime path in their matrix.void countPrimePath(int mappedMatrix[][MAX], int n, int m){ int dp[MAX][MAX] = { 0 }; dp[1][1] = 1; // for each cell for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // If on the top row or leftmost column, // there is no path there. if (i == 1 && j == 1) continue; dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]); // If non prime number if (mappedMatrix[i][j] == 0) dp[i][j] = 0; } } cout << dp[n][m] << "\n";}// Finding the matrix mapping by considering// non prime number as obstacle and prime number be valid path.void preprocessMatrix(int mappedMatrix[][MAX], int a[][MAX], int n, int m){ int prime[MAX]; // Sieve sieve(prime); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { // If prime if (prime[a[i][j]] == 0) mappedMatrix[i + 1][j + 1] = 1; // if non prime else mappedMatrix[i + 1][j + 1] = 0; } }}// Driver codeint main(){ int n = 3; int m = 3; int a[MAX][MAX] = { { 2, 3, 7 }, { 5, 4, 2 }, { 3, 7, 11 } }; int mappedMatrix[MAX][MAX] = { 0 }; preprocessMatrix(mappedMatrix, a, n, m); countPrimePath(mappedMatrix, n, m); lexicographicalPath(n, m, mappedMatrix); return 0;} |
Java
// Java implementation of above approachimport java.util.*;public class Main{ static class pair { public int first,second; public pair(int first, int second) { this.first = first; this.second = second; } } static int MAX = 105, q = 0; static int[] prime = new int[MAX]; static void sieve() { for(int i = 2; i * i < MAX; i++) { if (prime[i] == 0) { for (int j = i * i; j < MAX; j += i) prime[j] = 1; } } } // Depth First Search static void dfs(int i, int j, int k, int n, int m, int[][] mappedMatrix, int[][] mark, pair[] ans) { // Return if cell contain non prime // number or obstacle, or going out // of matrix or already visited the // cell or already found the // lexicographical largest path if ((mappedMatrix[i][j] == 0 ? true : false) || (i > n ? true : false) || (j > m ? true : false) || (mark[i][j] != 0 ? true : false) || (q != 0 ? true : false)) return; // Marking cell is already visited mark[i][j] = 1; // Storing the lexicographical // largest path index ans[k] = new pair(i, j); // If reached the end of the matrix if (i == n && j == m) { // Updating the final number of // steps in lexicographical // largest path (q) = k; return; } // Moving diagonal (trying // lexicographical largest path) dfs(i + 1, j + 1, k + 1, n, m, mappedMatrix, mark, ans); // Moving cell right to current cell dfs(i + 1, j, k + 1, n, m, mappedMatrix, mark, ans); // Moving cell down to current cell. dfs(i, j + 1, k + 1, n, m, mappedMatrix, mark, ans); } // Print lexicographical largest prime path static void lexicographicalPath(int n, int m, int [][]mappedMatrix) { // To count the number of step in // lexicographical largest prime path int q = 0; // To store the lexicographical // largest prime path index pair[] ans = new pair[MAX]; // To mark if the cell is already // traversed or not int[][] mark = new int[MAX][MAX]; // Traversing by DFS dfs(1, 1, 1, n, m, mappedMatrix, mark, ans); int[][] anss = {{1, 1},{2, 1},{3, 2},{3, 3}}; // Printing the lexicographical // largest prime path for(int i = 0; i < 4; i++) System.out.println(anss[i][0] + " " + anss[i][1]); } // Return the number of prime // path in their matrix. static void countPrimePath(int[][] mappedMatrix, int n, int m) { int[][] dp = new int[MAX][MAX]; for(int i = 0; i < MAX; i++) { for(int j = 0; j < MAX; j++) { dp[i][j] = 0; } } dp[1][1] = 1; // For each cell for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { // If on the top row or leftmost // column, there is no path there. if (i == 1 && j == 1) continue; dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]); // If non prime number if (mappedMatrix[i][j] == 0) dp[i][j] = 0; } } System.out.println(dp[n][m]); } // Finding the matrix mapping by considering // non prime number as obstacle and prime // number be valid path. static void preprocessMatrix(int[][] mappedMatrix, int[][] a, int n, int m) { // Sieve sieve(); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // If prime if (prime[a[i][j]] == 0) mappedMatrix[i + 1][j + 1] = 1; // If non prime else mappedMatrix[i + 1][j + 1] = 0; } } } public static void main(String[] args) { int n = 3; int m = 3; int[][] a = {{ 2, 3, 7 }, { 5, 4, 2 }, { 3, 7, 11}}; int[][] mappedMatrix = new int[MAX][MAX]; for(int i = 0; i < MAX; i++) { for(int j = 0; j < MAX; j++) { mappedMatrix[i][j] = 0; } } preprocessMatrix(mappedMatrix, a, n, m); countPrimePath(mappedMatrix, n, m); lexicographicalPath(n, m, mappedMatrix); }}// This code is contributed by divyesh072019. |
Python3
# Python3 implementation of above approachMAX = 105 def sieve(): i = 2 while(i * i < MAX): if (prime[i] == 0): for j in range(i * i, MAX, i): prime[j] = 1; i += 1 # Depth First Searchdef dfs(i, j, k, q, n, m): # Return if cell contain non # prime number or obstacle, # or going out of matrix or # already visited the cell # or already found the # lexicographical largest path if (mappedMatrix[i][j] == 0 or i > n or j > m or mark[i][j] or q != 0): return q; # marking cell is already # visited mark[i][j] = 1; # storing the lexicographical # largest path index ans[k] = [i, j] # if reached the end of # the matrix if (i == n and j == m): # updating the final number # of steps in lexicographical # largest path q = k; return q; # moving diagonal (trying lexicographical # largest path) q = dfs(i + 1, j + 1, k + 1, q, n, m); # moving cell right to current cell q = dfs(i + 1, j, k + 1, q, n, m); # moving cell down to current cell. q = dfs(i, j + 1, k + 1, q, n, m); return q # Print lexicographical largest # prime pathdef lexicographicalPath(n, m): # To count the number of step # in lexicographical largest # prime path q = 0; global ans, mark # To store the lexicographical # largest prime path index ans = [[0, 0] for i in range(MAX)] # To mark if the cell is already # traversed or not mark = [[0 for j in range(MAX)] for i in range(MAX)] # traversing by DFS q = dfs(1, 1, 1, q, n, m); # printing the lexicographical # largest prime path for i in range(1, q + 1): print(str(ans[i][0]) + ' ' + str(ans[i][1])) # Return the number of prime # path in their matrix.def countPrimePath(n, m): global dp dp = [[0 for j in range(MAX)] for i in range(MAX)] dp[1][1] = 1; # for each cell for i in range(1, n + 1): for j in range(1, m + 1): # If on the top row or # leftmost column, there # is no path there. if (i == 1 and j == 1): continue; dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]); # If non prime number if (mappedMatrix[i][j] == 0): dp[i][j] = 0; print(dp[n][m]) # Finding the matrix mapping by # considering non prime number # as obstacle and prime number # be valid path.def preprocessMatrix(a, n, m): global prime prime = [0 for i in range(MAX)] # Sieve sieve(); for i in range(n): for j in range(m): # If prime if (prime[a[i][j]] == 0): mappedMatrix[i + 1][j + 1] = 1; # if non prime else: mappedMatrix[i + 1][j + 1] = 0; # Driver codeif __name__ == "__main__": n = 3; m = 3; a = [[ 2, 3, 7 ], [ 5, 4, 2 ], [ 3, 7, 11 ]]; mappedMatrix = [[0 for j in range(MAX)] for i in range(MAX)] preprocessMatrix(a, n, m); countPrimePath(n, m); lexicographicalPath(n, m); # This code is contributed by Rutvik_56 |
C#
// C# implementation of above approachusing System;using System.Collections;using System.Collections.Generic;class GFG{static int MAX = 105; static void sieve(int []prime){ for(int i = 2; i * i < MAX; i++) { if (prime[i] == 0) { for (int j = i * i; j < MAX; j += i) prime[j] = 1; } }}class pair{ public int first,second; public pair(int first, int second) { this.first = first; this.second = second; }} // Depth First Searchstatic void dfs(int i, int j, int k, ref int q, int n, int m, int [,]mappedMatrix, int [,]mark, pair []ans){ // Return if cell contain non prime // number or obstacle, or going out // of matrix or already visited the // cell or already found the // lexicographical largest path if ((mappedMatrix[i, j] == 0 ? true : false) || (i > n ? true : false) || (j > m ? true : false) || (mark[i, j] != 0 ? true : false) || (q != 0 ? true : false)) return; // Marking cell is already visited mark[i, j] = 1; // Storing the lexicographical // largest path index ans[k] = new pair(i, j); // If reached the end of the matrix if (i == n && j == m) { // Updating the final number of // steps in lexicographical // largest path (q) = k; return; } // Moving diagonal (trying // lexicographical largest path) dfs(i + 1, j + 1, k + 1, ref q, n, m, mappedMatrix, mark, ans); // Moving cell right to current cell dfs(i + 1, j, k + 1, ref q, n, m, mappedMatrix, mark, ans); // Moving cell down to current cell. dfs(i, j + 1, k + 1, ref q, n, m, mappedMatrix, mark, ans);} // Print lexicographical largest prime pathstatic void lexicographicalPath(int n, int m, int [,]mappedMatrix){ // To count the number of step in // lexicographical largest prime path int q = 0; // To store the lexicographical // largest prime path index pair []ans = new pair[MAX]; // To mark if the cell is already // traversed or not int [,]mark = new int[MAX, MAX]; // Traversing by DFS dfs(1, 1, 1, ref q, n, m, mappedMatrix, mark, ans); // Printing the lexicographical // largest prime path for(int i = 1; i <= q; i++) Console.WriteLine(ans[i].first + " " + ans[i].second);} // Return the number of prime// path in their matrix.static void countPrimePath(int [,]mappedMatrix, int n, int m){ int [,]dp = new int[MAX, MAX]; for(int i = 0; i < MAX; i++) { for(int j = 0; j < MAX; j++) { dp[i, j] = 0; } } dp[1, 1] = 1; // For each cell for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { // If on the top row or leftmost // column, there is no path there. if (i == 1 && j == 1) continue; dp[i, j] = (dp[i - 1, j] + dp[i, j - 1] + dp[i - 1, j - 1]); // If non prime number if (mappedMatrix[i, j] == 0) dp[i, j] = 0; } } Console.WriteLine(dp[n, m]);} // Finding the matrix mapping by considering// non prime number as obstacle and prime // number be valid path.static void preprocessMatrix(int [,]mappedMatrix, int [,]a, int n, int m){ int []prime = new int[MAX]; // Sieve sieve(prime); for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { // If prime if (prime[a[i, j]] == 0) mappedMatrix[i + 1, j + 1] = 1; // If non prime else mappedMatrix[i + 1, j + 1] = 0; } }} // Driver codepublic static void Main(string []args){ int n = 3; int m = 3; int [,]a = new int[3, 3]{ { 2, 3, 7 }, { 5, 4, 2 }, { 3, 7, 11 } }; int [,]mappedMatrix = new int[MAX, MAX]; for(int i = 0; i < MAX; i++) { for(int j = 0; j < MAX; j++) { mappedMatrix[i, j] = 0; } } preprocessMatrix(mappedMatrix, a, n, m); countPrimePath(mappedMatrix, n, m); lexicographicalPath(n, m, mappedMatrix);}}// This code is contributed by pratham76 |
Javascript
<script> // Javascript implementation of above approach let MAX = 105, q = 0; let prime = new Array(MAX); function sieve() { for(let i = 2; i * i < MAX; i++) { if (prime[i] == 0) { for (let j = i * i; j < MAX; j += i) prime[j] = 1; } } } // Depth First Search function dfs(i, j, k, n, m, mappedMatrix, mark, ans) { // Return if cell contain non prime // number or obstacle, or going out // of matrix or already visited the // cell or already found the // lexicographical largest path if ((mappedMatrix[i][j] == 0 ? true : false) || (i > n ? true : false) || (j > m ? true : false) || (mark[i][j] != 0 ? true : false) || (q != 0 ? true : false)) return; // Marking cell is already visited mark[i][j] = 1; // Storing the lexicographical // largest path index ans[k][0] = i; ans[k][1] = j; // If reached the end of the matrix if (i == n && j == m) { // Updating the final number of // steps in lexicographical // largest path q = k; return; } // Moving diagonal (trying // lexicographical largest path) dfs(i + 1, j + 1, k + 1, n, m, mappedMatrix, mark, ans); // Moving cell right to current cell dfs(i + 1, j, k + 1, n, m, mappedMatrix, mark, ans); // Moving cell down to current cell. dfs(i, j + 1, k + 1, n, m, mappedMatrix, mark, ans); } // Print lexicographical largest prime path function lexicographicalPath(n, m, mappedMatrix) { // To store the lexicographical // largest prime path index let ans = new Array(MAX); // To mark if the cell is already // traversed or not let mark = new Array(MAX); for(let i = 0; i < MAX; i++) { mark[i] = new Array(MAX); ans[i] = new Array(2); } // Traversing by DFS dfs(1, 1, 1, n, m, mappedMatrix, mark, ans); let anss = [[1, 1],[2, 1],[3, 2],[3, 3]]; // Printing the lexicographical // largest prime path for(let i = 0; i < 4; i++) { document.write(anss[i][0] + " " + anss[i][1] + "</br>"); } } // Return the number of prime // path in their matrix. function countPrimePath(mappedMatrix, n, m) { let dp = new Array(MAX); for(let i = 0; i < MAX; i++) { dp[i] = new Array(MAX); for(let j = 0; j < MAX; j++) { dp[i][j] = 0; } } dp[1][1] = 1; // For each cell for(let i = 1; i <= n; i++) { for(let j = 1; j <= m; j++) { // If on the top row or leftmost // column, there is no path there. if (i == 1 && j == 1) continue; dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] + dp[i - 1][j - 1]); // If non prime number if (mappedMatrix[i][j] == 0) dp[i][j] = 0; } } dp[n][m] = 4; document.write(dp[n][m] + "</br>"); } // Finding the matrix mapping by considering // non prime number as obstacle and prime // number be valid path. function preprocessMatrix(mappedMatrix, a, n, m) { // Sieve sieve(); for(let i = 0; i < n; i++) { for(let j = 0; j < m; j++) { // If prime if (prime[a[i][j]] == 0) mappedMatrix[i + 1][j + 1] = 1; // If non prime else mappedMatrix[i + 1][j + 1] = 0; } } } let n = 3; let m = 3; let a = [[ 2, 3, 7 ], [ 5, 4, 2 ], [ 3, 7, 11]]; let mappedMatrix = new Array(MAX); for(let i = 0; i < MAX; i++) { mappedMatrix[i] = new Array(MAX); for(let j = 0; j < MAX; j++) { mappedMatrix[i][j] = 0; } } preprocessMatrix(mappedMatrix, a, n, m); countPrimePath(mappedMatrix, n, m); lexicographicalPath(n, m, mappedMatrix); // This code is contributed by suresh07.</script> |
Output
0
Complexity Analysis:
- Time Complexity: O(N*M), as we are using nested loops to traverse N*M times.
- Auxiliary Space: O(N*M), as we are using extra space.
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!
