Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
1,149 views

All past online assesments of Google can be found using the tag "google_oa" in the search bar.

Here is the link :  https://www.desiqna.in/tag/google_oa

in Online Assessments by Expert (35,210 points) | 1,149 views

1 Answer

0 like 0 dislike
You are given a matrix A having N rows and M columns. The rows are numbered from 1 to N from top to bottom and columns are numbered from 1 to M from left to right. You are allowed to move right and down only, that is if you are at cell (i, j), then you can move to (i+1, j) and (i, j+1). You are not allowed to move outside the matrix.

Your task is to find the number of good path starting from (1,1) to (N,M).
Good Path: If the sum of all the elements that lie in the path is divisble by K, then the path is considered as good.

Constraints
1 <= N, M <= 16
1 <= Ai, K <= 10^18

Sample Input
3
3
23
1 2 3
4 5 6
7 8 9

Sample Output
1

Explanation
N = 3, M = 3, K = 23
1->2->5->6->9, Sum is 23 which is divisble by 23 and there is only one good path in the above sample matrix, So the output is 1.
by Expert (35,210 points)