GATE CSE 1994 | Question: 7

Question

An array $A$ contains $n$ integers in locations $A[0], A[1], \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1\leq K \leq n-1$. An incomplete algorithm for doing this in linear time, without using another array is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared.

min:=n;
i=0;
while _____ do
begin
    temp:=A[i];
    j:=i;
    while ____ do
    begin
        A[j]:=____;
        j:=(j+K) mod n;
       if j<min then
        min:=j;
    end;
    A[(n+i-K)mod n]:=____;
    i:=______;
end;

Comments

The min gets updated only for i=0 and not for i=1 right

Answer 1

The inner loop is left rotating elements each separated by $k$ elements. i.e. A[i+k] goes to A[i], A[i+2k] goes to A[i+k] and so on.

This loop stops, when A[i] gets assigned to some place which should be A[n-k+i]. (we do not need mod n here because i < k)

If $n$ is a multiple of $K,$ the inner loop iterates $n/K$ times and outer loop iterates $K$ times.

Otherwise inner loop iterates more than $n/K$ times and correspondingly the outer loop gets adjusted using the min variable.  

min:=n;
i=0;
while i < min do
begin
    temp:=A[i];
    j:=i;
    while (j != n+i-K)  do //we completed a cycle when this equals
    begin
        A[j]:= A[(j+K) mod n];
        j:=(j+K) mod n;
        if j<min then //updates the iteration count for i loop
            min:=j;
    end;
    A[(n+i-K)mod n]:=temp; //we do not need mod n, because i is <= K
    i:= i+1;
end;

C code for the problem is as follows:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
    int *A;
    int n, i, j, K, min;
    time_t t;
    time(&t); //to get current time
    srand(t); //initialize random seed using current time
    printf("Please enter n and K: ");
    scanf("%d%d", &n, &K);
    A = malloc(n * sizeof(int));
    printf("Enter n elements: \n");
    for(i = 0; i < n; i++)
        A[i] = rand()%1000;
    printf("n elements are: \n");
    for(i = 0; i < n; i++)
        printf("%d ", A[i]);
    i = 0, min = n;
    while(i < min)
    {
        int temp = A[i];
        j = i;
        while(j != n+i-K)//we completed a cycle when this equals
        {
            A[j] = A[(j+K)%n];
            j = (j+K) % n;
            if(j < min) min = j;
        }
        A[n+i-K] = temp;
        i++;
    }
    printf("\nThe numbers left rotated by %d places are: \n", K);
    for(i = 0; i < n; i++)
        printf("%d ", A[i]);
    free(A);
}

Comments

@Arjun Isn't the inner loop running $\lfloor{n/K}\rfloor$ times?

---

while (j != n+i-K) do //we completed a cycle when this equals….….how it is detecting a cycle is completed ?

---

Take I/P array: 6,3,4,1,2. Here n = 5.

Now, if we cyclically rotate by say K = 3:-

Then a[4] will go to a[1],

a[3] will go to a[0],

a[2] will go to a[4],

a[1] will go to a[3] and

a[0] will go to a[2].

In other (easy way) we can interpret it as :-

$a[1] = a[4], a[0] = a[3], a[4] = a[2], a[3] = a[1], a[2] = a[0]$

 

At any point of time, we do two tasks:-

1. Update value of  A[j] = A[(j+K) mod n]; // a[0] = a[(0+3)%5] = a[3]
2. Update value of A[(n+i-K)mod n]:= temp; // a[(5+0-3)] = temp, i.e. a[2] = a[0] //as temp stored value of a[0]

Thus, (j!= n+i-K)  is the breaking condition as till then we update the two values

Answer 2

In this video i have solved the question and also this question has came in ISRO 2018 so i have taken mcqs option too watch it and subscribe my channel

https://youtu.be/J10tX-Y51dE