The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+1 vote

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]=_______;
  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;   
asked in Algorithms by Veteran (400k points)
edited by | 712 views

1 Answer

+9 votes
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.
answered by Loyal (9.5k points)
edited by
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.

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
49,434 questions
53,630 answers
70,900 users