407 views

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;

| 407 views

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);
}
by Veteran (416k points)
selected by

1
2