GATE CSE 1998 | Question: 2.14

Question

Let $A$ be a two dimensional array declared as follows:

A: array [1 …. 10] [1 ….. 15] of integer;

Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location $100$, what is the address of the element $A[i][j]$?

• A. $15i+j+84$

• B. $15j+i+84$

• C. $10i+j+89$

• D. $10j+i+89$

Comments

@Lakshman Patel RJIT

Are you sure that the column-major is $\mathbf{(D)}$?

---

@Satbir

Can you please verify that?

---

Yes, it is $\mathbf{D}$ only for Column-Major.

Answer 1

$A [ LB_1\ldots UB_1,LB_2\ldots UB_2]$

$BA =$ Base address.

$C =$ size of each element.

Row major order.

$Loc(a[i][j]) = BA + [(i-LB_1) (UB_2-LB_2 + 1) + (j - LB_2)] * C$.

Column Major order

$Loc(a[i][j]) = BA + [ (j-LB_2) (UB_1-LB_1+ 1) + (i - LB_1) ] * C$.

Substituting the values.

Answer is A.

Comments

@anchitjindal07

http://chortle.ccsu.edu/java5/notes/chap49c/ch49C_7.html

Hope it helps. 

---

What is LB1,LB2 and UB1 etc here ?

---

LB1 lower bound 1 array [1(LB1)....10(UB1)]

Answer 2

In this question, it is asked that A[i][j] is how many memory blocks far from memory location 100 (i.e base address of array). Now to reach 'i^th' row we have to pass through i-1 rows each of which contains 15 elements. After that to reach jth column (of i^th row) we have to pass through j-1 elements. 

Address of A[i][j] = base_address of A + [(i-1)*15 + (j-1)]*1

= 100 + 15i -15 + j - 1

=15i + j + 84

A is the answer. 

Answer 3

Let Array be : A[m][n]

Type 1 :

The array indices started with 1 and it is in Row major order :

Base Address + Size * [ (i-1)*n + (j-1) ]

The array indices started with 0 and it is in Row major order : 

Base Address + Size * [ i*n + j ]

Type 2 :

The array indices started with 1 and it is in Column major order :

Base Address + Size * [ (j-1)*m + (i-1) ]

The array indices started with 0 and it is in Column major order : 

Base Address + Size * [ j*m + i ]

Answer 4

$\color{blue}{\underline{\text{Most Easy Solution to this problem and applicable to all such problems:}}}$

$\color{blue}{\underline{\text{Explanation:}}}$

$\mathbf{\color{red}{Row\;Major\;Order:}}$

Let's convert the above arrays to indices which starts from $\mathbf{0}$.

$\therefore[1\dots10][1\dots15]\equiv[0\dots9][0\dots14]$

Now, we need to find the position of $\mathbf{\left (i,j\right)^{th}}$ element.

$\because$ We subtracted $\mathbf{1}$ from the above given arrays to make their starting indices $\mathbf{0}$.

$\therefore \mathbf{ \left (i, j\right) } \equiv \mathbf{\left(i-1,j-1\right)}$.

Now,

$\therefore\mathbf{Address} = \mathrm{\underset{Base\;address}{100} + \underset{No.\;of\;rows}{(i-1)}\times\underset{\text{No. of columns in each row.}}{15}+\underset{\text{Number of cols. we need to traverse after rows}}{j-1} \\= 100+15\times i-15+j-1 \\=84+15\times i+j \\= 15i+j+84 }$

$\therefore\;\mathbf{15i+j+84}$ is the required answer. Hence, $\mathbf{Option-A}$ is corect.

---

$\color{red}{\mathbf{Column\;Major\;Order:}}$

$\color{red}{\mathbf{\underline{Swap\;column\;to\;rows\;and\;rows\;to\;columns:}}}$

Let's convert the above arrays to indices which starts from $\mathbf{0}$.

$\therefore[1\dots10][1\dots15]\equiv[0\dots9][0\dots14]$

On Swapping column to rows and rows to column:

$[0\dots14][0\dots9]$

Now, we need to find the position of $\mathbf{\left (i,j\right)^{th}}$ element.

$\because$ We subtracted $\mathbf{1}$ from the above given arrays to make their starting indices $\mathbf{0}$.

$\therefore \mathbf{ \left (i, j\right) } \equiv \mathbf{\left(i-1,j-1\right)}$.

On swapping:

$\mathbf{(j-1,i-1)}$

Now,

$\therefore\mathbf{Address} = \mathrm{\underset{Base\;address}{100} + \underset{No.\;of\;rows}{(j-1)}\times\underset{\text{No. of columns in each row.}}{10}+\underset{\text{Number of cols. we need to traverse after rows}}{i-1} \\= 100+10\times j+i-1 \\=89+10\times j+i \\= 10j+i+89}$

$\therefore\;\mathbf{10j+i+89}$ is the required answer.

$\therefore \mathbf{D}$ is the correct option in case of $\mathbf{Column\;Major\;Order}$.

 

Comments

This is a very good and easy explanation.