Google | OA Coding Questions and Solutions | Set - 14 | 2022

Question

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

Answer 1

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.