The Gateway to Computer Science Excellence
+7 votes
Consider a 2 dimensional array A[40...95,40...95] in lower triangular matrix representation. The size of each element of array is 1 Byte.If array is implemented in memory as Row major,with base address as 1000,the address of A[66][50] is .....

Ans. 1361
in DS by Loyal (7k points) | 704 views
Please explain general methodology for solving it :)
please represent using pen and paper that how it is represented in matrix not able to visualize it.

4 Answers

+14 votes
Best answer

In general for RMO we calculate like :

Let A[LR.....UR][Lc.....Uc]  be a 2D array

Address of A[i][j]= Base + Size of each element { (no. of rows fully covered before reaching row i x no. of columns in each row) + no. of elements covered in the current row i}

no. of rows fully covered = (i-LR)

no. of columns in each row= (Uc-Lc+1)

But here the case is a bit different. The elements are arranged in lower triangular matrix form like this:

The rows are not fully covered.

The 1st row has 1 element.

The 2nd row has 2 elements. The 3rd has 3 elements and so on.

So kth row will have k elements.

No. of elements covered upto k rows is 1+2+3....k = k(k+1)/2.

We need to find address of A[i][j]. To reach this row no. i we have to cover previous (i-LR) rows.

So, no. of elements covered in (i-LR) rows is ((i-LR)* (i-LR+1))/2 rows
Now we are at row no. i.

No. of elements covered in this row no. i is (j-Lc)  elements.

Address of A[i][j]= Base + size( ((i-LR)* (i-LR+1))/2  + (j-Lc))

Address of A[66][50] = 1000 + 1 ( (66-40)*(66-40+1)/2 + (50-40) ) = 1000 + (26*27/2 + 10 ) = 1000 + (351+10) =1361


We need to find address of A[66][50]. To reach this row no. 66 we have to cover (66-40)= 26 rows.

So, no. of elements covered in 26 rows = 26*(26+1)/2 = 351

Now we are at row no. 66.

No. of elements covered in this row is (50-40) = 10.

Address of A[66][50] = 1000 + (351+10) =1361

by Boss (23.5k points)
selected by
@MINIPanda can you please explain the normal formula approach for  both row and column major,i.e row major : B+w{n(i-L1)+(j-L2)) and column major : B+w{n(j-L2)+(i-L1)}  how to access these
is this type of questions are present in gate ?
will u give some pictorial representation for the given array?

@suneetha The one that is already given in the question..


I think it should be $1362$. there are $66-40+1$ rows before $A[66]$. Shouldn't it be?


How many rows are there before A[41]? 41-40=1 row isn't it? Similarly, there are (i-40) rows before A[i].


@MiNiPanda Okay, thanks. sorry to disturb you on the trivial thing. seems I was outta my mind. 

Its okay :)
+1 vote


$Size\ of\ element=1\ B$


$\\ =1000+\left \{\underbrace {66-40=26}+(50-40) \right \}\times 1B$

                    $Natural\ \#\ sum\\ of\ 26\ rows$

$=1000+\left \{ \dfrac{26\times 27}{2}\ +\ 10 \right \}\times 1B$

$=1000+\left \{ 351+10 \right \}\times 1B$

by Active (4.1k points)
+1 vote


$40^{th}\ row=1$

$41^{st}\ row=2$

$42^{nd}\ row=3$




$66^{th}\ row=26$


Now you are standing on $66^{th}$ row and it's first element will start from $40^{th}$ column but you need to go to $50^{th}$ column, hence add $11(40,41,42....50)$



But index starts from $0,$ so subtract $1$

by Active (4.1k points)
0 votes
I think answer should be 2466 because given array is 2 dimensional then doesn't matter it is lower triangular,upper triangular or diagonal matrix as all 0's also require 1 B of memory,hence the address of A[66][50] will be:

1000+[(50-40)+(95-40+1)*(66-40)] = 2466
by (11 points) 1 flag:
✌ Low quality (Hira Thakur)

Related questions

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
50,737 questions
57,309 answers
105,022 users