The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
374 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;
asked in Algorithms by Veteran (59.9k points) | 374 views

1 Answer

+2 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);
}
answered by Veteran (400k points)
selected ago by

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
186,007 comments
70,899 users