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