# 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:

Very optimise solution..