5,524 views
7 votes
7 votes
Consider a 2D array with elemnts stored in the form of lower triangular matrix.The elements must be crossed to read A[4,2] from the array [-6..................+8 , -6..........+8 ] is

4 Answers

Best answer
10 votes
10 votes

A 2D matrix is a lower triangular matrix if all the elements in above the main diagonal are zero.

Given the matrix as $A[-6..................+8 , -6..........+8 ]$ which looks like

So here we have to calculate the number elements crossed from starting to reach at $A[4,2]$, we are assuming elements are stored in row major order.

To reach $A[4,2]$, let us calculate how many rows are completely filled above the desired element which is 10 rows and in each successive row elements increased by 1. So till 10 rows we can say sum of 10 natural numbers is the number of elements till 10th row which is $\frac{10*11}{2}$=55 elements.

Element $A[4,2]$ is in 11th row, till now we have calculated 55 elements and now in 11th row number of elements before it are $2-(-6)$ =8 elements.

Finally we have to cross $55+8=63$ elements to reach $A[4,2]$.

Hence 63 is the correct answer


If we want to find the address of an element $A[i,j]$ in lower triangular matrix $A[lb_{1}.........ub_{1}][lb_{2}.........ub_{2}]$ stored in row major order it is calculated  as 

$Add(A[i,j])=Base \ address+[1+2+3+...sum \ of\ (i-lb_{1}) terms+(j-lb_{2})]*width$

selected by
5 votes
5 votes

In general #f elements to be crossed if array is given A[lb1...ub1][lb2...ub2]

  A[i][j] = (i-lb1)(i-lb1+1)/2 + j-lb2

In given A[-6..................+8 , -6..........+8 ]

#f elements to cross to access A[4][2] = (4-(-6))(4-(-6)+1)/2 + 2-(-6) = 63 elements

edited by
2 votes
2 votes
$a[-6....+8][-6....+8]$

$BA=1000(assumed)$

$Size\ of\ element=1\ B(assumed)$

$Loc[4][2]$

$\\ =1000+\left \{\underbrace {4-(-6)=10}+(2-(-6)) \right \}\times 1B$

                    $Natural\ \#\ sum\\ of\ 10\ rows$

$=1000+\left \{ \dfrac{10\times 11}{2}\ +\ 8 \right \}\times 1B$

$=1000+\left \{ 55+8 \right \}\times 1B$

$=1063B$

No related questions found