841 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;

| 841 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
selected by
+1

@Arjun sir

couldn't understand this. Any reference for this ?

0
can someone please explain this? I tried doing this with an example and still couldn't understand.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.2580028474330902, "perplexity": 5914.201061302036}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-29/segments/1593655891884.11/warc/CC-MAIN-20200707080206-20200707110206-00288.warc.gz"}