JUGGLING ALGORITHM

In the previous post we have seen two approach to rotate an arraY.

In this we will learn about juggling algorithm

 Juggling algorithm is one of the most efficient algorithm for the rotation of an array by d times. 

1.This algorithm is divide the array into sets/parts.

2We can find the no of parts by taking the GCD(n,k) where n is the size of array and k is the no of rotation of by k times.

3.After getting the sets ,move the elements within the sets just like in-place algorithm(without extra space).

Now the main question arise to user mind is why we are  taking gcd of no and how  it will be divided if the number are odd?

CASE 1:NUMBER IS EVEN 

Lets say if the number are  n=6   where 1<=n<=6 and 2 this number is equally divided and its form a  subarray of size 2

NOTE: here i am moving rotating the array towards right

so we can say our subarray are [1,2] [3,4],[5,6]  we can assume each subarray to be splitted into different parts and we can simply shift the first subarray i.e 1,3,5 right and our subarray become 

[5,2],[1,4],[3,6], now we have one more subarray index left i.e 2,4,6  so we can simply shift right and 

our final subarray become [5,6],[1,2],[3,4].Now we do not have any index of subarray left so we can print our answer= [5,6,1,2,3,4],

 

CASE 2:NUMBER IS ODD

Lets say if the number are  n=7  where 1<=n<=7 and 2  if we try to divide the number it spilt into 

[1,2,3],[4,5,6],[7] into 3 subarray of unequal size he our approach will become wrong for the solution. because if we try to shift each index subarray as we have done previously  we cannot shift because subarray 7 has just element ,So the better approach to use this problem is use GCD operation as this method always divide into equal parts.

so now gcd of (7,2)=1so we can assume as a one subarray of [1,2,3,4,5,6,7]  and we simply shift the arr[i+k]to arr[i].

let understand through example 

here in the given array we first find the gcd of the number(n,k) and split it into equal parts  then simply 

replace the array value to its new value without using an extra space.

after iterating for the first index move to the 2nd index and again try to split into equal  parts in the same way after all value are shifted simply print the answer .

INPUT
6  2
1 2 3 4 5  6
OUTPUT
5 6 1 2 3 4

INPUT
7 2
1 2 3 4 5 6  7
OUTPUT
6 7 1 2 3 4 5

Here is code of this😀

#include<bits/stdc++.h>
    using namespace std;
    
            
         void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k %= n;
        k = n-k; //right shift
       // cout<<k;
        int j, temp, d;
        for(int i=0; i < __gcd(n, k); i++) {
            temp = nums[i];
            j = i;
            while(true) {
                d = (j + k) % n;
                if( d == i ) 
                    break;
                nums[j] = nums[d];
                j = d;
                //cout<<nums[j];
            }
            nums[j] = temp;
        }
         }
    
    int main()
    {
        int n,k;
        cin>>n>>k;
      vector<int>v;
        for(int i=0;i<n;i++)
        {
         int x;
         cin>>x;
         v.push_back(x);
        }
       rotate(v,k);
        for(int i=0;i<n;i++)
        {
            cout<<v[i]<<" ";
        }
    }

Thanks for reading the article😊