Juggling Algorithm for array rotation using java
By Anubhav SrivastavaHi 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..