The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+30 votes
4.2k views

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:

  1. $i+j$
  2. $i+j-1$
  3. $(j-1)+\frac{i(i-1)}{2}$
  4. $i+\frac{j(j-1)}{2}$
asked in DS by Veteran (59.5k points)
edited by | 4.2k views
0
fix it plzz question is not loading.
0
Could anyone explain it clearly by giving one example without any ambiguity ?
+10
in a lower triangular matrix, i th row contains (i +1) number of non zero  elements.

Let's count how many elements are there before arr[i,j]----> If we assume array index starts from 0 then,

before i th row there are i rows(row 0 to  i-1) , and in total these rows has 1+2+3.....+i =i(i+1)/2 elements(row 0 has 1 element, row 1 has 2 elements, .... row i-1 has i elements)

Now at i row, before j th element there are j elements(starting from arr[i,0] to arr[i,j-1]),

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

0 to (i(i+1)/2 + j -1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have  index i(i+1)/2 + j in this new single dimensional compact array.

But none of the option is  i(i+1)/2 + j, Actually, they have considered array indexes starting from 1 .

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.....+(i-1)= i((i-1)/2 elements(row 1 has 1 element, row 2 has 2 elements, .... row i-1 has i-1 elements)

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

1 to (i(i-1)/2 + j-1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have  index i(i-1)/2 + j in this new single dimensional compact array. Answer C.
0
@Bikram sir pls give example for this
0
Read all the comments and see the snap posted by @srestha in the comments below best answer.
0
@ Sourav Basu  Can you please elaborate the below lines

1 to (i(i-1)/2 + j-1) in the new compact array, hence the very next element arr[i,j] (of the old lower triangular matrix) will have  index i(i-1)/2 + j in this new single dimensional compact array. Answer C.
0
0
Fix this please or mention in question somewhere it's wrong. Wasted an hour of mine
0
@sutanay3
In this new compact representation, (i,j) th element of the  old lower triangular matrix will have (i(i-1)/2 + j-1) elements
before it  so, it's own index  will be  (i(i-1)/2 + j-1) + 1.

It's like if you are standing in a queue and there are 9 people standing before you then, your own position from the starting of the queue will be 10.

9 Answers

+36 votes
Best answer

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

So, C is the correct answer.

PS: Though not mentioned in question, from options it is clear that 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.....+(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]$) .

Henc,e 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 .

answered by Boss (14.3k points)
edited by
+1
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..
0
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 .
0
Please explain with the example....
+4

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

0
@srestha Why do you assume that array index starts from 1 and not 0?
0
it is more close to option
0
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.
0
@srestha I guess it is working only when in both cases array index starts from 1.
0
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
+1
@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.
0
yes ..
0
@srestha How the row number is 5 if we take array index starting from 1.Mine it is coming to be 4. Please explain.
0
yes, but we never start array index from 1
+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.
+2
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.
0
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.
+13 votes
answer is C...... it is (j-1) + i(i-1)/2  when indices start from 1 ( as we guess from the options )
answered by Boss (19.7k points)
edited by
+12
Yes. The correct answer here is (j-1) + i(i-1)/2 . It is when the indices start with 1 , And when indices start with 0, Answer is j+i(i+1)/2
+1
What will be the expression for column major ??
0
here  i= row and j= column right?
0

L_(ij)={a_(ij)   for i>=j; 0   for i<j.

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

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

0
plzz explain wid an exmaple..m unable 2 understand..i have doubts in arrays..
+6 votes
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
answered by Active (4.3k points)
0
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)
0
Option updated . It is to be assumed that indexing starts from 1
+5 votes
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)
answered by Junior (727 points)
+3 votes
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.
answered by Boss (15.9k points)
+2 votes

Although best answer contain all information but i want to demonstrate by example lets take one example of 3x3 lower triangular matrix

1 0 0
2 3 0
4 5 6

now above matrix is stored on following basis in new representation

1 2 3 4 5 6

Now to find index of (i,j)th element by assuming that both array representations are starting from 1.

now lets find the location of element (2,2) by all options

A) i+j = 2+2 = 4 (wrong)

B) i+j-1 = 2+2-1 =3 (right) but check for (3,1) and it will give the same answer so (wrong).

C) (j-1) + i(i-1)/2 = 1 + 2.1/2 =2 (wrong)

D) i + j(j-1)/2 = 2 + 2.1/2 =3 (right) check for (3,1) also it will give the same answer so (wrong).

So clearly no option is matching  either answer should be j + i(i-1)/2 or if new array representation will start from 0 then answer will be C.

 

 

answered by Active (3.1k points)
+1 vote

Let Matrix indices are of form  1st row -->11 12 13 14....1n

                                                2nd row--> 21 22 23 23...2n,  

Therefore number of non zero elements present in row1 = 1, row 2 =2 , row3 =3 .....row i = i

Number of non zero elements before ith row = 1+2+3+.....i-1 =  i(i+1)/2

Now array starts from index 0. To store i(i+1)/2 elements in array, indexes used will be   {i(i+1)/2} -1 as array starts from 0th index.

Now, we have 'j' more elements to cross to reach(i,j), so the index of (i,j) will be {i(i+1)/2} -1 +j = {i(i+1)/2} +j-1

Therefore Answer is C

answered by Active (1.4k points)
+1 vote

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

answered by (33 points)
0 votes

Answer Would be C if you go by Default representation of Array and Matrix i.e  Array starts with index 0 and matrix starts with 1
Plz note that matrix A[0,0] representation is NOT actually representing MATRIX but it is representing value stored in ARRAY of MATRIX at location 1,1. 

answered by (239 points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,529 questions
46,674 answers
139,821 comments
57,589 users