+1 vote
712 views

An array $A$ consists of $n$ integers in locations $A[0], A[1], \ldots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $k$ places, where $1<=k<=(n-1)$. An incomplete algorithm for doing this in linear time, without using another array is given bellow. Complete the algorithm by filling in the blanks.

min=n; i=0;
while(_________) {
temp= A[i]; j=i;
while(_________) {
A[j]= _______;
j=(j+k) mod n;
if(j<min) then
min = j;
}
A[(n+i-k) mod n]=_______;
i=________;

}
1. i>min;            j !=(n+1) mod n ;        A[j+k]                     temp:     i+1;
2. i<min;            j !=(n+i) mod n ;         A[j+k]                     temp:     i+1;
3. i>min;            j !=(n+i+k) mod n ;      A[j+k]                     temp:     i+1;
4. i>min;            j !=(n+i-k) mod n ;     A(j+k) mod n]         temp:     i+1;
edited | 712 views
0

In the five blanks given in the question the last two blanks must be $temp$ and $i+1$ because all the given options for the fourth and fifth blanks has $temp$ and $i+1$.

Now,for the first blank it must be$i<min$because if it is $i>min$ then the control goes out of the while loop in the initial case when i=0 and min=n

So,the first blank is i<min which implies either option B or option D is correct.

Assume option B is correct then in the bracket of while we have j!= (n+i) mod n

That means whenever j becomes equal to (n+i)mod n then control goes out of the while loop.

Now (n+i)mod n = i and j is always equal to i because in the line 3 of the code we are assining the value of i to j.

So, if option B is true control never enters the second while loop but it has to enter the second while loop to shift the nos. K places left.

Hence, option D is correct.
edited
0
All other options are wrong, but does it make option D correct? 😄
0

Sir please edit the question. The question written is wrong. Actual question is given below.

0
I am trying to put an explanation why option D is correct.
0
Fine now? It's actually a GATE1994 question.

1
2