recategorized by
27,907 views
75 votes
75 votes

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}$
recategorized by

11 Answers

Best answer
89 votes
89 votes

$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 .

edited by
19 votes
19 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
17 votes
17 votes
answer is C...... it is (j-1) + i(i-1)/2  when indices start from 1 ( as we guess from the options )
edited by
11 votes
11 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.
Answer:

Related questions

29 votes
29 votes
6 answers
1
Kathleen asked Oct 5, 2014
4,888 views
An array $A$ contains $n$ integers in non-decreasing order, $A \leq A \leq \cdots \leq A[n]$. Describe, using Pascal like pseudo code, a linear time algorithm to find $...
35 votes
35 votes
4 answers
2
Kathleen asked Oct 4, 2014
22,919 views
Linked lists are not suitable data structures for which one of the following problems?Insertion sortBinary searchRadix sortPolynomial manipulation
33 votes
33 votes
6 answers
3
Kathleen asked Oct 4, 2014
33,092 views
Which of the following permutations can be obtained in the output (in the same order) using a stack assuming that the input is the sequence $\text{1, 2, 3, 4, 5}$ in that...