In a compact one-dimensional array representation for a lower triangular…

20171994

In a compact one-dimensional array representation for a lower triangular matrix (all elements above the diagonal are zero) of size n x n, non-zero elements of each row are stored one after another, starting from the first row, the index of (i, j)th element in this new representation is

  1. A.

    i + j

  2. B.

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

  3. C.

    i + j - 1

  4. D.

    i + j(j - 1)/2

Attempted by 626 students.

Show answer & explanation

Correct answer: B

Formula: j - 1 + i(i - 1)/2. So, option B is the correct answer.

Note: The formula in option B assumes that matrix subscripts (i, j) start from 1, while the compact one-dimensional array index starts from 0.

Explanation: In a lower triangular matrix, row 1 has 1 non-zero element, row 2 has 2 non-zero elements, row 3 has 3 non-zero elements, and so on. Before the ith row, the total number of stored elements is 1 + 2 + ... + (i - 1) = i(i - 1)/2.

Within the ith row, the element (i, j) has (j - 1) stored elements before it. Therefore, the zero-based index of element (i, j) in the compact array is i(i - 1)/2 + (j - 1). Hence, option B is correct.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Isro