The Gateway to Computer Science Excellence

+3 votes

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;

+6 votes

Best answer

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); }

52,345 questions

60,484 answers

201,815 comments

95,291 users