The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+10 votes
880 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
asked in DS by Veteran (59.7k points)
recategorized by | 880 views
0
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.

2 Answers

+18 votes
Best answer

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
answered by Veteran (370k points)
selected by
+4
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 votes
A:=A[0,0]    B:=(i<n)    C:=(j<n-1)   D:=i++
answered by Active (4.2k points)
0
Should'nt j be j<n instead of j<n-1?
+3

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++).

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

44,510 questions
49,968 answers
165,822 comments
65,915 users