ISRO2018-12

Question

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=________;
    
}

$\begin{array}{lllll}
\text{a.}&i>\min;&  j !=(n+1) \mod n;& A[j+k]& \text{temp};& i+1; \\     
\text{b.}&i<\min; &  j !=(n+i)\mod n;& A[j+k]& \text{temp};&  i+1; \\
\text{c.}&i>\min;& j !=(n+i+k) \mod n; & A[j+k] & \text{temp};& i+1; \\      
\text{d.}&i<\min; & j !=(n+i-k) \mod n;& A[(j+k) \mod n]& \text{temp};& i+1;
\end{array}$

Comments

https://gateoverflow.in/2503/gate1994-7

Answer 1

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 have $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 line 3 of the code we are assigning 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.

Comments

All other options are wrong, but does it make option D correct? 😄

---

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

---

I am trying to put an explanation why option D is correct.

---

Fine now? It's actually a GATE1994 question.

---

sir for option D , It should be i < min (First blank).

---

yes you are correct