Circular Array Rotation

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***** 

Read More