4k views

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]$?

1. $15i+j+84$

2. $15j+i+84$

3. $10i+j+89$

4. $10j+i+89$

in DS
edited | 4k views
+11

Row Major Order: $A[1.....n1][1.....n2]$
A[i][j] = Base Address + ( (i-1)*no._of_columns + (j-1))*element_Size

Column Major Order: $A[1.....n1][1.....n2]$
A[i][j] = Base Address + ((j-1)*no._of_rows + (i-1))*element_size

+2
Row-Major Order answer is $(A)$ and Column Major Order answer is $(D)$
0

@Lakshman Patel RJIT

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

0

@Satbir

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

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

edited
+13

Yes, in row-major addresses will be like below.

 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 159 160 100 + (i-1)15 + (j-1) 174 175 189 190 204 205 219 220 234 235 249
0

@Gate Keeda Sir will it be always true that in declaration like following, 10 is number of rows and 15 is number of columns

array [1 …. 10] [1 ….. 15]
0
0
What is LB1,LB2 and UB1 etc here ?
0
LB1 lower bound 1 array [1(LB1)....10(UB1)]

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 'ith' row we have to pass through i-1 rows each of which contains 15 elements. After that to reach jth column (of ith row) we have to pass through j-1 elements.

= 100 + 15i -15 + j - 1

=15i + j + 84

by

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 ]

by

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

by
edited by
0

This is a very good and easy explanation.

+1 vote

$a$        $\underbrace{[10]}$            $\underbrace{[15]}$

$streets$       $buildings$

Now you want to go and meet a friend who lives on $j^{th}$ building of $i^{th}$ street means $a[i][j]$

So, firstly cross $(i-1)$ streets each consist of $15$ buildings: $(i-1)\times 15=15i-15$

Now cross $(j-1)$ buildings in order to reach your destination: $j-1$

$Ans: RMO: 100+15i-15+j-1=>15i+j+84$

$a$        $\underbrace{[10]}$            $\underbrace{[15]}$

$buildings$       $streets$

Now you want to go and meet a friend who lives on $i^{th}$ building of $j^{th}$ street means $a[i][j]$

So, firstly cross $(j-1)$ streets each consist of $10$ buildings: $(j-1)\times 10=10j-10$

Now cross $(i-1)$ buildings in order to reach your destination: $i-1$

$Ans: CMO: 100+10j-10+i-1=>10j+i+89$

+1 vote

When the initial element of the array is at A[0][0] to reach A[i][j] we skip i rows and j columns.

But here, the initial element is at A[1][1]. So, we'll skip (i-1) rows and (j-1) columns.

$100+(i-1)*15+(j-1)$

=> $100+15i-15+j-1$

=> $84+15i+j$

Option A