The Gateway to Computer Science Excellence
+24 votes
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 by
edited by | 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

Can you please verify that?

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

6 Answers

+30 votes
Best answer

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

by
edited by
+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
What is LB1,LB2 and UB1 etc here ?
0
LB1 lower bound 1 array [1(LB1)....10(UB1)]
+22 votes

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. 

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. 

by
+11 votes

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
+2 votes

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

by
+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

by
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
52,315 questions
60,436 answers
201,777 comments
95,257 users