GATE CSE 1994 | Question: 1.11

Question

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size $n \times n$, non-zero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, the index of the $(i, j)^{th}$ element of the lower triangular matrix in this new representation is:

• A. $i+j$
• B. $i+j-1$
• C. $(j-1)+\frac{i(i-1)}{2}$
• D. $i+\frac{j(j-1)}{2}$

Comments

If we assume the starting index in "compact single dimensional array" is 1.

Then in option C : j + i(i-1)/2 should have been given

---

may be easy 

---

If it is 0-indexed, the answer should be (j - 1) + (i(i + 1)) / 2

If it is 1-indexed, the answer should be j + (i(i - 1)) / 2

Answer 1

$j-1 + i(i-1)/2$  because if you form a lower triangular matrix it contains elements in rows $1,2,3,\ldots$ 

So, C is the correct answer.

PS: Though not mentioned in the question, from options it is clear that the array index starts from $1$ and not $0.$

Explanation :

In a lower triangular matrix, $i^{th}$ row contains $(i +1)$ number of non zero  elements.

If we assume Array index starting from $1$ then, $i^{th}$ row contains $i$ number of non zero elements.

before $i^{th}$ row there are $i -1$ rows (row $1$ to  $i-1$) , and in total these rows has $1+2+3+\ldots +(i-1)= i((i-1)/2$ elements (row $1$ has $1$ element, row $2$ has $2$ elements, row $i-1$ has $i-1$ elements  etc.)

Now, at $i^{th}$ row, before $j^{th}$ element there are $(j-1)$ elements(starting from $arr[i,1]$ to $arr[i,j-1]$) .

Hence, in total before $arr[i,j]$ there are $(i(i-1)/2 + j-1)$ elements and those elements will have indexes .

S,o the index of the $(i,j)^{th}$  element of the lower triangular matrix in this new representation is  $(j-1) + i(i-1)/2$ which is option C .

Comments

Can You please tell me why it is not j + i(i+1)/2 . Array index should start with 0 generally rgt? So to get A[2][1] , 2 rows have to be crossed, so (1+2) elements in lower triangular matrix and then j. So am having a doubt here, how i(i-1)/2, it should be i(i+1)/2 rgt? Please help me in my doubt. ThankYou..

---

Can u plz explain this sum logic once again , we should be summing up the columns , why rows ?Although calculations are fine but still logic is confusing me ,plz clarify this .

---

Please explain with the example....

---

if we want a(3,2) from the array below

then row number of 1D array will be $2+\frac{(3\times 2)}{2}=5$

which is correct

---

@srestha Why do you assume that array index starts from 1 and not 0?

---

it is more close to option

---

Please clarify on 2 things:

1. Which index to start 0(zero) or 1(one)? In both place : Matrix and memory

2. Made easy booklet, C option seems to be different compared to gateoverflow options. So which are correct option and correct answer with respect to correct selection of index in every case?

Note : Please describe memory visualization of given scenario of question. It will be helpful a lot.

Please share your views and make solution with no conflicts.

Thanks GO.

---

@srestha I guess it is working only when in both cases array index starts from 1.

---

means?

Actually I think it is a simple question like from starting what is the xth number non zero element of 2D array, if we represent it in 1D array. Isnot it @Ahwan

---

@srestha what I said is.. Draw a lower triangular 2D array with index starting from one.  Then in 1D array.. Start from one too. Do not write the zeros...  Option C satisfied.  Yes simple one.

---

yes ..

---

@srestha How the row number is 5 if we take array index starting from 1.Mine it is coming to be 4. Please explain.

---

yes, but we never start array index from 1

---

@srestha Yes but in the previous comment ,it is told to start both 1D array and 2D array with 1 . Actually I think it should be j instead of (j-1).  http://gateforum.com/wp-content/uploads/2013/01/CS-1994.pdf

Or we can start 1 with the matrix and 0 with the 1D array. Then we will get the desired answer.

---

The answer should be j + i*(i -1)/2. The reason is that the returned formula gives the index for the element (i,j -1), we should have added j directly. This question came in ISRO 17 paper too.

---

According to the explanation there will be (j-1)+i*(i-1)/2 elements before the element (i,j), now if our single dimension array also starts with index 1 then the index of (i,j)th element in the single dimension array formed will be j+i*(i-1)/2 and if the index starts with index 0 then the index will be  (j-1)+i*(i-1)/2. I think the question needs more clear explanation.

---

(d) is the correct option not (c). Take 3*3 lower triangular matrix and try to eliminate the option then you will get option (d) as correct option.

---

 

Hence, Option C is the answer.

---

Why did u consider all elements in the ith row. We have to take only those elements which are part of lower triangular matrix. So it should be A[i,i], A[i,i+1],.........,A[i, j]. So we should add only j-i+1 to i(i-1)/2.

---

@ Bhagirath
Awesome explanation, Thank you very much. It's been a long time I was searching for a good explanation. 😊

---

yes amazing explanation

---

Don’t confuse we have to store elements of MATRIX to 1D ARRAY.

Matrix starts with 1 but the 1D array starts with 0. Now read the solution.

---

if i and j both are 1 then index will be 0 but it is assumed to be starting from 1 ,So how this solution is correct?

---

Nice. But why do not we store the zeros? Lower triangular doesn't it need to save the zeros(on the upper part).

---

Because we already know the upper part will be all zeros. This method saves space.

---

Okay. Thankyou bro.

---

Note: The 2D lower triangular matrix has indexes starting from $1$ but the new 1D array that we make is starting from $0$.

---

Option C is correct If these Two Assumptions are Correct . 

• If the 2D Matrix Index starts from 1 , therefore first element will be at i = 1, j = 1
• and If 1D Array containing elements in compact form will have index starting from 0 . 

Correct me if I am wrong . 

---

Don't we have to multiply it with the size of the array element

---

@Mayuri27

no need to multiply by the size of array. As mentioned in the question we are storing only non-zero elements of the $2-D\space Array$.

Answer 2

option (c)

Explanation:
An example of lower triangular matrix of size 3 x 3 is given below.
1   0   0
2   3   0
4   5   6
While storing we will store as 1 2 3 4 5 6.
Index of the  (i,j)th element = the number of elements in (i - 1) rows + j
                                          = (1 + 2 + ... + i-1) + j
                                          = [i(i-1)/2] + j
Hence option (c)
Note:
* The number of elements in (i - 1) rows  = 1 + 2 + ... + i-1, because first row contains only 1 element, second row contains only 2 elements, third row contains only 3 elements and so on.
* 1 + 2 + ... + n = n(n-1)/2

Comments

although, I agree with you but option c contains : (j-1) + i(i-1)/2
your answer would be true if matrix have indexing starting from zero,i guess (still confuse although)

---

Option updated . It is to be assumed that indexing starts from 1

Answer 3

answer is C...... it is (j-1) + i(i-1)/2  when indices start from 1 ( as we guess from the options )

Comments

help me guys can't able to get formula how can we generate it formula?

(j-1) + i(i-1)/2 ???????????/how 

---

plzz explain wid an exmaple..m unable 2 understand..i have doubts in arrays..

---

Start 1 as an index for matrix and 0 as an index for the 1D array. Then we will get the desired answer.

Answer 4

Option C in actual gate paper is correct. See the explanation below.

Comments

Yes, I was wondering the same thing. Replacing (j-1) with only J gives correct answer for both type of indexing. Not sure if in the actual paper without -1 was there.

Answer 5

Whole trick to this question is to guess if array start with 1 or zero. As they have not mentioned you have to consider both the cases and then go by the concept of row major.
First case:

if array start with zero then we have to cross n rows and j number of element in the last column. As each row will be containing elements in increasing order like 1st row will contain 1 non zero element. 2 will 2 non zero. So total number of element we have to cross can be represented as the sum of natural numbers.
so if array start with zero you will can get address with   i(i+1)/2 + j

similarly if it start with 1 replace i and j with (i-1) and j-1 respectively.
You will get option C.

Answer 6

An example of lower triangular matrix of size 3 x 3 is given below.
1   0   0
2   3   0
4   5   6
While storing we will store as 1 2 3 4 5 6.
Index of the  (i,j)th element = the number of elements in (i - 1) rows + j
                                          = (1 + 2 + ... + i-1) + j
                                          = [i(i-1)/2] + j
Hence option (c)