edited by
661 views
0 votes
0 votes
hi i got this question in an interview question can anyone provide me the algorithm to this.

You've got a table of size N*M containing positive integers. We'll consider the table rows numbered from top to bottom 1 through N, and the columns numbered from left to right 1 through M. Then we'll denote the cell in row x and column y as (x,y).

Initially cell (1,1) contains one turtle named Mona. Mona wants to get to cell (N,M). Some cells of the table have obstacles. A cell is considered to be containing an obstacle if value of the cell is a NON-PRIME NUMBER. That means that Mona can only move through PRIME Numbers. It is guaranteed that upper left corner (1,1) contains a prime number.

Mona can go from cell (x,y) to one of three cells (x+1,y ), ( x ,y+1 ) and ( x + 1, y + 1 ) only if the required cell doesn't contain an obstacle. Help him find the number of ways in which it can go from cell (1,1) to cell (N,M).

In addition, you need to print the lexicographical largest path to reach cell (N,M).

Note: A cell (x1,y1) is lexicographical larger than another cell (x2,y2) if either x1>x2 or if x1=x2 and y1>y2. A path X is lexicographical larger than another path Y, if the first cell that does not match is lexicographical larger in X than in Y.

For example, cell (3,2) is lexicographical larger than cell (3,1).
Let, Path Y: (1,1)(2,1)(3,1)(3,2)(3,3)
Path X: (1,1)(2,1)(3,2)(3,3)
Path X is lexicographical larger than another path Y, because the first cell that does not match (i.e. (3,2) in X and (3,1) in Y) is lexicographical larger in X than in Y.

Input Format

The first line contains two space separated integers, N (number of rows) and M (number of columns).

Then N lines follow, each containing M space separated integers.

Constraints

1 <= N,M <= 103
2 <= A[x][y] <= 105 (the elements of the matrix)

Output Format

In the first line, print the total number of possible ways to reach (N,M) from (1,1). Since this number may be too large, print the answer modulo 109 +7.

Print the cell indexes (space separated) of each step of his lexicographically largest path in a new line .
If no path exists, only print 0 in first line.

(See sample test case for clarification)

Sample Input
3 3
2 3 7
5 4 2
3 7 11
Sample Output
4
1 1
2 1
3 2
3 3
edited by

1 Answer

0 votes
0 votes

hi i got this question in an interview question can anyone provide me the algorithm to this.

You've got a table of size N*M containing positive integers. We'll consider the table rows numbered from top to bottom 1 through N, and the columns numbered from left to right 1 through M. Then we'll denote the cell in row x and column y as (x,y).

Initially cell (1,1) contains one turtle named Mona. Mona wants to get to cell (N,M). Some cells of the table have obstacles. A cell is considered to be containing an obstacle if value of the cell is a NON-PRIME NUMBER. That means that Mona can only move through PRIME Numbers. It is guaranteed that upper left corner (1,1) contains a prime number.

Mona can go from cell (x,y) to one of three cells (x+1,y ), ( x ,y+1 ) and ( x + 1, y + 1 ) only if the required cell doesn't contain an obstacle. Help him find the number of ways in which it can go from cell (1,1) to cell (N,M).

In addition, you need to print the lexicographical largest path to reach cell (N,M).


Note: A cell (x1,y1) is lexicographical larger than another cell (x2,y2) if either x1>x2 or if x1=xand y1>y2. A path X is lexicographical larger than another path Y, if the first cell that does not match is lexicographical larger in X than in Y.

For example, cell (3,2) is lexicographical larger than cell (3,1).  
Let, Path Y: (1,1)(2,1)(3,1)(3,2)(3,3) 
Path X: (1,1)(2,1)(3,2)(3,3) 
Path X is lexicographical larger than another path Y, because the first cell that does not match (i.e. (3,2) in X and (3,1) in Y) is lexicographical larger in X than in Y.

Input Format

The first line contains two space separated integers, N (number of rows) and M (number of columns).

Then N lines follow, each containing M space separated integers.

Constraints

1 <= N,M <= 103 
2 <= A[x][y] <= 105 (the elements of the matrix)

Output Format

In the first line, print the total number of possible ways to reach (N,M) from (1,1). Since this number may be too large, print the answer modulo 109 +7.

Print the cell indexes (space separated) of each step of his lexicographically largest path in a new line . 
If no path exists, only print 0 in first line.

(See sample test case for clarification)

Sample Input 
3 3 
2 3 7 
5 4 2 
3 7 11 
Sample Output 

1 1 
2 1 
3 2 
3 3

guys ...........can anyone solve this probem it's very urgent for my interview today 6pm

plz if any one can solve this problem mail me solution on my Email id- [email protected]

Related questions

0 votes
0 votes
0 answers
1
Sajal Mallick asked Nov 27, 2023
171 views
As we have to select maximal set of “non overlapping” activities. So like job scheduling algo of greedy we can solve it. So according to that complexity must be O(n l...
0 votes
0 votes
1 answer
3
Ray Tomlinson asked Aug 9, 2023
425 views
How many times is the comparison $i >= n$ performed in the following program?int i = 200 n = 80; main() { while (i >= n) { i = i - 2 n = n + 1 } }