# Circular Array Rotation

Standard

### In this post i will  explain the Circular array rotation problem in the most efficient way. Here is the problem statement taken directly from hackerrank.com.

Here is the trick. We will consider 2 cases, 1st is  when k<m and 2nd is when k>m, you will get to know why we are considering these two cases as we go on.
1. Let the input parameters be n, k=4 and m=5, so the numbers would be (1,2,3,4,5,6,7,8,9...n-1,n) keep note of the number at index m-k (i.e. at index 1). Now after  k=4  rotations  the resulting numbers will be (n-3,n-2,n-1,n,1,2,3,4 ...n-5,n-4). Note that the current number at index m=5(which in this case is 2) was at an index  1 (i.e. at m-k). So we can directly find the element at index m=5 without actually rotating the array by outputting the element at index (m-k).
2. Now let k=4 and m=3. In this case the number that is at index m=3 was actually at an index (n-k+m). Here also we can find the element at m=3 without rotating the array by outputting the element at index (n-k+m).
In case you are wondering what about the case when k>n well we can tackle that by using the mod(%) operator.For those of you who do not know how mod(%) operator works. Basically it returns the remainder, let k=r%n, so if rotation(i.e. r) is greater than n, due to the mod(%) operator the value of k will be remainder of r/n. e.x. if r=9, n=6 than k=3 and if r is multiple of n i.e. if r=5,10,15,20..... and n=5 than k=0 after the operation.
Here is my code.

#include <iostream>
using namespace std;
int main() {
int n,k,q,m,j;
cin>>n>>k>>q;
k%=n;                       /* Or k=k%n which will make sure that the rotation is in circular manner. The  mod(%) operator returns the remainder so if rotation(i.e. k) is greater than n, due to the mod(%) operator the value of k will be remainder of k/n. e.x. if k=9, n=6 than k=3 after this operation and if k is multiple of n i.e. if k=5,10,15,20..... and n=5 than k=0 after the operation. */
int *A= new int[n]                          /*  OR int A[n] ---initializing an array A of size n . To know more about the format and it's use search for dynamic array  */
for(int i=0;i<n;i++) cin>>A[i];                         /* filling the array */
for(int i=0;i<q;i++){
cin>>m;                                  /* taking the index */
j=m-k;
if(j<0) cout<<A[n+j]<<endl;         /* the case when k>m. The output is A[n+j] which is nothing but A[n+m-k]. */
else cout<<A[j]<<endl;                    /* the case when k<m. The output is A[j] which is nothing but A[m-k]. */
}
return 0;
};

*****IF YOU WANT ME TO EXPLAIN A PERTICULAR PROBLEM THAN PLEASE LEAVE A LINK TO THE PROBLEM IN THE COMMENT*****

1. very clear explanation, thank you so much...

1. My pleasure :)

2. #include
#include

int main(){
long int n;
long int k,l;
long int *a,*b,a_i;

scanf("%ld %ld %ld",&n,&k,&l);

a = (long int*)malloc(n * sizeof(int));

b = (long int*)malloc(l * sizeof(int));

for( a_i = 0; a_i < n; a_i++){
scanf("%ld",&a[((k+a_i)% n)]);
}

for(a_i=0;a_i<l;a_i++){

scanf("%ld",&b[(a_i)]);

}

for( a_i = 0; a_i < l; a_i++){
printf("%ld\n",a[ b[a_i] ]);

}

return 0;
}

whats wrong with my code , i don't understand it only satisfies single case

2. int main(){
int n;
int k;
int q;
int j;
cin >> n >> k >> q;
vector a(n);
for(int a_i = 0;a_i < n;a_i++){
cin >> a[a_i];
}
j = k%n;
for(int a0 = 0; a0 < q; a0++){
int m;
cin >> m;
if((m-j)<0)
cout << a[m-j+n];
else
cout << a[m-j]<<endl;
if(a0+1 < q)
cout << endl;
}

return 0;
}

Can you tell me what is wrong my logic? Except for the sample test and test case 15, all the others fail. It is really bugging me now. Any insight would be greatly helpful! Thanks

1. Hi!!

This is the mistakes in your code.
1. In the part "cout << a[m-j] << endl;" in the else statement. It should be "cout<<a[m-j];" .That "endl" is not needed since and hence it is causing error .
"if(a0+1 < q)
cout << endl;"
is already taking care of it.

1. While writing the code try to optimize it. Check that you are not doubling any calculation. E.g. in your code you are doubling this "(m-j)" calculating operation. Instead you could have just used an extra variable as say "z=m-z ". It is not that significant but still it's a good practice.
Note that there are various ways to optimize a code, not computing something multiple times is one of them.

2. This part of your code

"if(a0+1 < q)
cout << endl;"

is not necessary. You are making the processor do some extra work of comparing " a0+1 and q " each time. Instead you could have just put an "endl" in the if else statement like this

"if((m-j)<0)
cout << a[m-j+n]<<endl;
else
cout << a[m-j]<<endl;".

Hope it helped you :)

3. wow, thanks a lot this has really helped me to understand circular arrays.

1. Also I am planing to put a tutorial for you guys so keep checking this blog. This tutorial will not be like any reference book instead i will explain the topics the way i understood it, so that you will be able to grasp it much easily.

4. I am not able to understand the case where m<k.when k=4 and m=3 , the element at index m=3 is n, which was at n before rotation.

5. I am not able to understand the case where m<k.when k=4 and m=3 , the element at index m=3 is n, which was at n before rotation.

1. The index of n was n-1( which is nothing but n-k+m for k=4 and m=3) since in array the index starts from 0 and goes till n-1.

6. int n = in.nextInt();
int k = in.nextInt();
int q = in.nextInt();
int[] a = new int[n];
int[]b=new int[n];
for(int a_i=0; a_i < n; a_i++){

a[a_i] = in.nextInt();
}
for(int j = 0; j < k; j++)
{
b=a[n-1];
for(int i=0;i<n-1;i++)
{
b[i+1]=a[i];
}
a=b.clone();
}
for(int i=0;i<q;i++)
{
int m=in.nextInt();
System.out.println(a[m]);
}

WHY DOESNT THIS WORK FOR SOME TEST CASES?

7. for k>m I used the logic m = (k + m - 1)%n. but i get errors. can u point out my mistake? thank u.

1. 8. Excellent Dinesh!

1. Thanks e-M@x :)

9. Thank! Great explanation :)

10. 11. Brilliant...!!! Worked like a charm... :)

12. int main(){
int n,j;
int k;
int q;
int a[n];

scanf("%d %d %d",&n,&k,&q);
k%=n;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
for(int i=0;i<q;i++){
int m;
scanf("%d",&m);
j=m-k;
if(j<0)
printf("%d",a[n+j]);

else
printf("%d",a[j]);
}
return 0;
}
it shows segmentation fault..!!tell me problem.
help me..

1. Hi!!
I didn't find anything which should give segmentation fault error.It ran fine without any error when i tried running it.Although you have done a minor mistake, which is
The printf in the if-else statement should contain "/n" so that every output is in the next line.

13. int main(){
int n;
int k;
int q;
scanf("%d %d %d",&n,&k,&q);
int a;
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a[a_i]);
}
for(int a0 = 0; a0 < q; a0++){
int m,j;
scanf("%d",&m);
j=m-k;
if(j<0) printf("%d\n",a[n+j]);
else printf("%d\n",a[j]);
}

return 0;
}
compilation is successful but it gives segmentation fault after submission.Please find error...
help me

14. int main(){
int n;
int k;
int q;
scanf("%d %d %d",&n,&k,&q);
int *a=(int*)malloc(sizeof(int)*n);
for(int a_i = 0; a_i < n; a_i++){
scanf("%d",&a[a_i]);
}
for(int a0 = 0; a0 < q; a0++){
int m;
scanf("%d",&m);

if((m-k)<0) printf("%d\n",a[n+m-k]);
else printf("%d\n",a[m-k]);
}

return 0;
}
segmentation fault is only in test case 4 and other case is perfect.

1. just write a statement " k=k%n"
after assigning the values of k and n

2. sry..im a beginner in coding can u tell me why should we add k=k%n statement...can u plss explain me clearly

3. Hi Bhakyalashmi!!
If the statement k=k%n is not there than for a large value of "k" let's say k=100 and small value of "n", let's say, n=10. As "m" has to be less than or equal to "n"(since it is the index) so let's take it as 10, than the statement "cout<<a[n+m-k] "
OR "cout<<a[m-k]"
will give error because the size of our array is "n" (which is less than "n+m-k" or "m-k" in our example) , since we are trying to access an index which is not there.

Hope it helped you :)

15. Awesome explanation and elegant solution. Thanks!
Btw, do you have similar challenges. I am a newbie to C and very bad at algorithms. I want to learn more!

16. excellent solution ...like a pro..
but how did you get this idea ...

17. #include
using namespace std;

int main ()
{
long int n,k,q,m;
cin>>n>>k>>q;
long int arr[n];
for(long int i=0;i>arr[i];
}
while(q--)
{
cin>>m;
long int pos=m;
if(k%n==0)
pos=(pos+k)%n;
else
pos=(pos+k-1)%n;
cout<<arr[pos]<<endl;
}
}

whats wrong in the code?

18. Why am I getting this error when I have not even touched main() ?

Here's my function code

int i,j,arr[queries_count];
*result_count=queries_count;
k = k % a_count;
for(i=1;i<=queries_count;i++)
{
j=queries[i]-k;
if(j<0)
arr[i]=a[a_count+j];
else
arr[i]=a[j];
}
return arr;
}

Segmentation Fault
Error (stderr)

GDB trace:
[New LWP 2592]
Core was generated by `solution'.
Program terminated with signal SIGSEGV, Segmentation fault.
#0 fprintf (__fmt=0x400cc4 "%d", __stream=0x155d010)
at /usr/include/x86_64-linux-gnu/bits/stdio2.h:97
97 return __fprintf_chk (__stream, __USE_FORTIFY_LEVEL - 1, __fmt,
#0 fprintf (__fmt=0x400cc4 "%d", __stream=0x155d010)
at /usr/include/x86_64-linux-gnu/bits/stdio2.h:97
#1 main () at solution.c:97

19. I know it is very much late. Sorry for that. But I got error of time out. even I ran my code in code blocks IDE it does't respond. and from all test cases only 6 problems are not accepting solution and giving error. I have input of that cases also. If you can Help me pls help. I am beginner and just joined collage. It will very kind of you if you help me sir. I am posting my code below.

CODE:

#include
using namespace std;

int main()
{

long long int i,j,u,n,k,m,p;

cin>>n;
cin>>k;
cin>>m;

long long int a[n],b[m];

for(i=0;i>a[i];
}

for(i=0;i>b[i];
}

k=k%n;

for(u=0;u=0;j--)
{
a[j]=a[j-1];
}

a=p;
}

for(i=0;i<m;i++)
{
cout<<a[b[i]]<<endl;
}

}

If you want test case input I will post that also