10 September 2016

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

30 comments:

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

    ReplyDelete
    Replies
    1. #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

      Delete

  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

    ReplyDelete
    Replies
    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.


      ***Some advice***
      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 :)

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

    ReplyDelete
    Replies
    1. Glad it helped you :)

      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.

      Delete
  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.

    ReplyDelete
  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.

    ReplyDelete
    Replies
    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.

      Delete
  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[0]=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?

    ReplyDelete
  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.

    ReplyDelete
    Replies
    1. Sorry for the late reply. Can you please post your code since i don't know what you have written in your "cout" after applying your logic.

      Delete
  8. Brilliant...!!! Worked like a charm... :)

    ReplyDelete
  9. 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..

    ReplyDelete
    Replies
    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.

      Delete
  10. int main(){
    int n;
    int k;
    int q;
    scanf("%d %d %d",&n,&k,&q);
    int a[10];
    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

    ReplyDelete
  11. 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.

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

      Delete
    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

      Delete
    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 :)

      Delete
  12. 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!

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

    ReplyDelete
  14. #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?

    ReplyDelete
  15. 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:
    Reading symbols from solution...done.
    [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

    ReplyDelete
  16. 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[0]=p;
    }


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

    }


    If you want test case input I will post that also

    ReplyDelete