Mr. Evan has given to his students an assignment where they need to multiply two boolean matrices and write the resultant matrix. Boolean matrix multiplication is done in the same way as standard matrix multiplication except for in the resultant matrix any entry which is not zero is treated as one.
Mr. Evan is tired of checking the correctness of their results, so he has asked you for help.
Given three N X N boolean matrices A, B and C, you need to write a code to determine whether A x B = C.
NOTE: There need not be a deterministic algorithm so you need to come up with a better probabilistic algorithm to get accepted.
Matrix A
0 0 0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 0 1
Matrix B
1 0 0 0 0
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0
0 0 0 0 0
Matrix C
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
Approach-
Here we don't need to do actual multiplication. We can identify all matrix A elements having 1's and matrix B elements having 1's. So in the above - A has 1 in (4, 3) and B in (3, 2). Here A col and B row are same (3). So the resultant matrix C would have 1 in (4, 2).
Solution
No comments:
Post a Comment