1.3k views

The following Pascal program segments finds the largest number in a two-dimensional integer array $A[0\dots n-1, 0\dots n-1]$ using a single loop. Fill up the boxes to complete the program and write against $\fbox{A}, \fbox{B}, \fbox{C} \text{ and } \fbox{D}$ in your answer book Assume that max is a variable to store the largest value and $i, j$ are the indices to the array.

begin
max:=|A|, i:=0, j:=0;
while |B| do
begin
if A[i, j]>max then max:=A[i, j];
if |C| then j:=j+1;
else begin
j:=0;
i:=|D|
end
end
end

in DS
recategorized | 1.3k views
+1
Have you got the answer to this?? Because I am unable to detect max if it is @ A[0,1]

If you found the answer, kindly post it here. Thanks.

We have to traverse all elements in array. The code is doing this row wise.

begin
max:=A[0,0], i:=0, j:=0;
while (i < n) do
begin
if A[i, j]>max then max:=A[i, j];
if (j < n-1) then j:=j+1;
else begin
j:=0;
i:=i++;
end
end
end
by Veteran (434k points)
selected by
+6
Arjun sir, just small correction for shake of accuracy, In if condition we need to check for j<n-1 otherwise it will go out of bound.
0
As we are acheving this answer using one loop. So this complexity of this code is O(n) ?

But still we willl be accessing n^2 elements. Any comment plz?
0
For loop is still running for n^2 times. Number of loops doesn't matter if it's running constant number of times, but if you have a single Loop running for n^2 or n^3 it matters.
0
I think (C) should be : j<n instead of j<n-1.

Please explain why it is n-1
+2
@Ayush.

j will be incremented till n-1. So last time when j=n-2 , increment happens and it becomes n-1.
0
nice explanation @Arjun sir
0
if we put in place of A max=-1 then also code will work same.
0
Correct. Even in case of max = 0 it will work the same. Since, negative number representation has an overhead, 0 is better. Either is better than A[0,0] as that saves from additional reading of [0,0] element. That element is being read first time in the loop anyway.
0
We can do max=INT_MIN also right ?
+1 vote
A:=A[0,0]    B:=(i<n)    C:=(j<n-1)   D:=i++
by Active (4.2k points)
0
Should'nt j be j<n instead of j<n-1?
+5

No, j shouldn't be j<n; rather it must be j<n-1.

Reason : j should be incremented(i.e. j++) so that we reach till n-1(last element in the row), after which we should make j=0(first element in the next row since i++).