 # Juggling algorithm for array rotation | Faceprep

Juggling algorithm is one of the efficient algorithms used for array rotation. Now, let us see about juggling algorithm and a program to rotate an array using the same algorithm.

## Juggling Algorithm

• In this method, divide the array into M sets, where M = GCD (n, k), and then rotate the elements in each set.
• From the number of elements ( n ) of the array and number of rotations ( k ) to be made to the array, the GCD(n, k) number of blocks are made.
• Then in each block, shifting will take place to the corresponding elements in the block.
• After all the elements in all the blocks are shifted, the array will be rotated for the given number of times.
• For Example: If we want to rotate the below array by 2 positions.

1 2 3 4 5 6

1.            M = GCD(6, 2) = 2;
2.            Initial Array : 1    2    3    4    5    6
3.            First Set Moves : 5    2    1    4    3    6
4.            Second Set Moves : 5    6    1    2    3    4            //  The array is rotated  twice.

## C++ program to rotate an array using Juggling algorithm

`#include<bits/stdc++.h>using namespace std;/*Function to get gcd of a and b*/int gcd(int a, int b) // gcd(a,b) number of blocks are formed{ if (b == 0) return a; else return gcd(b, a % b);}/*Function to left rotate array by n - number of rotations*/void array_left_rotate(int arr[], int d, int n){ int i, j, k, temp; for (i = 0; i < gcd(d, n); i++) // gcd(d,n) times the loop will iterate { /* move i-th values of blocks */ temp = arr[i]; j = i; while (1) { k = j + d; if (k >= n) // The element has to be shifted to its rotated position k = k - n; if (k == i) // The element is already in its rotated position break; arr[j] = arr[k]; j = k; } arr[j] = temp; }}int main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr); // Finding the size of the array cout<<"\nArray elements before rotating : \n"; for(int i = 0; i < n; i++) { cout<<arr[i]<<"\t"; // Printing the array elements } int no_of_rotations = 2; // Number of rotations to take place array_left_rotate(arr, no_of_rotations, n); cout<<"\n\nArray elements after rotating : \n"; for(int i = 0; i < n; i++) { cout<<arr[i]<<"\t"; // Printing the array elements after rotation of elements } cout<<"\n"; return 0;}`

OUTPUT ## Java program to rotate an array using Juggling algorithm

`public class Main{ /*Fuction to get gcd of a and b*/ public static int gcd(int a, int b)  {  if (b == 0)  return a;  else return gcd(b, a % b);  } /*Function to left rotate array of by d number of rotations*/ public static void leftRotate(int arr[], int d, int n)  {  int i, j, k, temp;  for (i = 0; i < gcd(d, n); i++) // gcd(d,n) times the loop will iterate {  /* move i-th values of blocks */ temp = arr[i];  j = i;  while (true) {  k = j + d;  if (k >= n) // The element has to be shifted to its rotated position k = k - n;  if (k == i) // The element is already in its rotated position break;  arr[j] = arr[k];  j = k;  }  arr[j] = temp;  }}  //  Main function public static void main(String[] args)  {  int arr[] = { 1, 2, 3, 4, 5, 6, 7 };  int no_of_rotations = 2; int n = arr.length; System.out.println("Array Elements before rotating : ");  for(int i = 0 ; i < n ; i++) { System.out.print(arr[i]+ " "); // Printing elements before rotation } leftRotate(arr, no_of_rotations, n);  System.out.println("\nArray Elements after rotating : ");  for(int i = 0 ; i < n ; i++) { System.out.print(arr[i] + " "); // Printing elements after rotation } } } `

## Python program to rotate an array using Juggling algorithm

`def leftRotate(arr, d, n):  for i in range(gcd(d, n)): # gcd(d, n) times the loop iterates  # move i-th values of blocks  temp = arr[i]  j = i  while 1:  k = j + d  if k >= n: # The element have to be rotated k = k - n  if k == i: # The element is already in rotated position break arr[j] = arr[k]  j = k  arr[j] = temp # Function to get gcd of a and b def gcd(a, b):  if b == 0:  return a;  else:  return gcd(b, a % b) #gcd(d,n) blocks are made  # Main Functionimport array as arrarr = arr.array('i', [1,2,3,4,5,6,7]) n = len(arr)no_of_rotations = 2print("Array Elements before rotation : ")for i in range (0, n):  print (arr[i], end = ' ')  leftRotate(arr, no_of_rotations, n )print("\nArray Elements after rotation : ")for i in range (0, n):  print (arr[i], end = ' ') `

### Relevant exercises

POST A NEW COMMENT

• Input (stdin)

Output (stdout)

Input (stdin)

Expected Output

Compiler Message

Input (stdin)

`2    3`

`5`
`5`
`5`