Juggling Algorithm for array rotation using java

Hi coders! I am back with a new problem which is related to a  famous data Structure Array. Many of you people definitely have solved the array rotation problem. There are various methods to rotate an array. So, here is a very efficient algorithm known as Juggling Algorithm to rotate an array with some d elements. This algorithm is based on GCD (Greatest Common Divisor) or HCF(Highest Common Factor).

Methods to implement Juggling algorithm

• First of all, divide the array by finding the GCD of d and n where d is the number of elements by which the array has to be rotated and n is the size of the array.
• GCD or HCF of d and n is the number of sets in which the array has to be divided.
• Move the elements within these numbers of sets.

Here is an example to understand better :

Let an array be like arr[] = {1,2,3,4,5,6,7,8,9} which is to be rotate  by d = 3 elements. Here n = 9 and d = 3 so GCD is 3.

After elements moved in the first set, the array is like : {4,2,3,7,5,6,1,8,9}

After elements moved in the second set, the array is like: {4,5,3,7,8,6,1,2,9}

Finally, after elements moved in the third set, the array is like: {4,5,6,7,8,9,1,2,3}

Below is the code to rotate array using juggling algorithm in Java

/* Java program for   left rotating an array by  
  some d elements */ 
class ArrayRotation { 
    /* Method to  rotate  an array of size n by d elements */
   private void rotateLeft(int array[], int d, int n) 
    { 
        int i, j, m;
         int temp; 
        int g_c_d = HCF(d, n);    // method call to calculate HCF of d and n
// HCF is same as GCD
        for (i = 0; i < g_c_d; i++) { 
            temp = arr[i]; 
            j = i; 
            while (true) { 
                m = j + d; 
                if (m >= n) 
                    m = m - n; 
                if (m == i) 
                    break; 
                arr[j] = arr[m]; 
                j = m; 
            } 
            arr[j] = temp; 
        } 
    } 
  
   
  
    /* method for  printing  an array */
    void printArr(int arr[]) 
    { 
        
        for (int i = 0; i < arr.length(); i++) 
            System.out.print(arr[i] + " "); 
    } 
  
    // method to calculate HCF of d and n
    int HCF(int d, int n) 
    { 
        if (n == 0) 
            return d; 
        else
            return HCF(n,d%n); 
    } 
  
    // main  functions 
    public static void main(String[] args) 
    { 
        ArrayRotation rotate = new ArrayRotation(); 
        int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; 
        rotate.rotateLeft(arr, 3, 9); 
        rotate.printArr(arr); 
    } 
} 
//code is provided by Anubhav Srivastava

Output:

4 5 6 7 8 9 1 2 3

Time complexity

Hence the time complexity of rotating an array by juggling algorithm is O(n).
Hope you like the solution to rotate an array using juggling algorithm in Java.

Also read:

• Java Program to Left Rotate an Array
• Search an element in a sorted and rotated array using Java