Software Engineer

You are given two water jugs with capacities X and Y litres respectively. Both the jugs are initially empty. There is an infinite amount of water supply available. The jugs do not have markings to measure smaller quantities.

The following operations are allowed:

• Fill any of the jugs entirely with water.
• Empty any of the jugs.
• Pour water from one jug into another till the other jug is full, or the first jug itself is empty.

You are required to tell whether it is possible to measure exactly ‘Z’ litres using both of the jugs.

If Z litres of water is measurable, you must have Z litres of water contained within one or both buckets by the end.

For example:

In order to measure 2 litres from jugs of 4 and 6 litres we can follow the following steps-

• Fill 6-litres jugs to its maximum capacity.
• Pour water from 6-litres jug to the jug with 4-litres capacity.
• Pour water from 6-litres jug to the jug with 4-litres capacity.

Ninja has been given two sparse matrices ‘MAT1’ and ‘MAT2’ of integers having size ‘N’ x ‘M’ and ‘M’ x ‘P’, respectively.

A sparse matrix is a matrix that contains very few non-zero elements.

Ninja has to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’. As Ninja is busy with some other tasks so he needs your help. Can you help Ninja to find the matrix formed by the multiplication of ‘MAT1’ and ‘MAT2’?

Note: The number of columns in ‘MAT1’ i.e ‘M’ is equal to the number of rows in ‘MAT2’ i.e ‘M’. It means we can always multiply ‘MAT1’ with ‘MAT2’.

For example:

For the ‘MAT1’ and ‘MAT2’ given below, ‘MAT3’ is the matrix formed by multiplying ‘MAT1’ and ‘MAT2’. 

1. MAT3[0][0] = MAT1[0][0] * MAT2[0][0] + MAT1[0][1] * MAT2[1][0]  ie. 2 * 1 + 1 * 4 = 6
2. MAT3[1][0] = MAT1[1][0] * MAT2[1][0] + MAT1[1][1] * MAT2[1][0] ie. 0 * 6 + 0 * 4 = 0