GATE Overflow Test Series | Mock GATE | Test 1 | Question: 39

Question

Alice is fond of doing programming, she usually takes part in different coding contest and mostly get gold medal because of the efficiency of her codes. Out of curiosity to know whether Alice is as that much capable in programming or not his sister has given her a program. She said “There are $2$ matrices $P$ and $Q$ both of order $5 \times 5, P$ is lower triangular matrix and $Q$ is upper triangular matrix, you have to find the product of $P$ and $Q$ i.e., $PQ$ and print the minimum number of algebraic operations used, but mind it, the program has to be as efficient as possible”. What will be the value printed by Alice’s program?

• A. $225$
• B. $110$
• C. $85$
• D. $55$

Answer 1

As the question asked for minimum algebraic operations, so when a number is to be multiplied with zero, it will not be counted.

Consider the following example:

$P = \begin{bmatrix} 1 & 0 & 0 & 0& 0 \\ 2 & 2 & 0&  0 & 0 \\ 3 & 3 & 3 & 0 & 0 \\ 4 & 4 & 4 & 4 & 0 \\ 5 & 5 & 5 & 5 & 5 \end{bmatrix}$

$Q = \begin{bmatrix} 5 & 5 & 5 & 5 & 5 \\ 0 & 4 & 4 & 4 & 4 \\ 0 & 0 & 3&  3 & 3 \\ 0 & 0 & 0 & 2 & 2  \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix}$

For first row and first column only multiplication of $1$ with $5$ will be considered, rest will be ignored.

For second row and second column, only multiplication of $2 \times 5$ and $2 \times 4$ will be considered, rest will be ignored.

So, $\begin{bmatrix} 1,0 & 1,0 & 1,0 & 1,0 & 1,0  \\ 1,0 & 2,1 &2,1 &2,1 &2,1 \\ 1, 0 & 2, 1 & 3,2 & 3,2, & 3,2 \\ 1,0 & 2,1 & 3,2 & 4,3 & 4,3 \\ 1,0 & 2,1 & 3,2 & 4,3 & 5,4 \end{bmatrix}$

$x \rightarrow $ number of multiplications

$y \rightarrow$ number of addition

The sum comes out to be $85.$

Comments

@gatecse Sir , is their any other way to solve this problem more quickly as this seems to be time consuming .

---

Easy but lengthy question.

Answer 2

[ 1 1 1 1 1

  1 3 3 3 3

  1 3 5 5 5

  1 3 5 7 7

  1 3 5 7 9

]

Total operations I have written for each element in PQ , only counted non zero values only for the ans
Do it for 1 row , 2 row u will find a pattern
Now add all this u will end up with 85