Juggling Algorithm for Array Rotation

Last Updated : 27 Aug, 2025

Given an array arr[], the task is to rotate the array by d positions to the left using juggling algorithm.

Examples:

Input: arr[] = {1, 2, 3, 4, 5, 6}, d = 2
Output: {3, 4, 5, 6, 1, 2}
Explanation: After first left rotation, arr[] becomes {2, 3, 4, 5, 6, 1} and after the second rotation, arr[] becomes {3, 4, 5, 6, 1, 2}
Input: arr[] = {1, 2, 3}, d = 4
Output: {2, 3, 1}
Explanation: The array is rotated as follows:
After first left rotation, arr[] = {2, 3, 1}
After second left rotation, arr[] = {3, 1, 2}
After third left rotation, arr[] = {1, 2, 3}
After fourth left rotation, arr[] = {2, 3, 1}

Approach:

The idea behind Juggling Algorithm is that we can rotate all elements of array using cycles. Each cycle is independent and represents a group of elements that will shift among themselves during the rotation. If the starting index of a cycle is i, then next elements of the cycle will be present at indices (i + d) % n, (i + 2d) % n, (i + 3d) % n ... and so on till we reach back to index i.
So for any index i, we know that after rotation we will have arr[(i + d) % n] at index i. Now, for every index in the cycle, we will place the element which should be present at that index after the array is rotated.

How many independent cycles will be there if an array of size n is rotated by d positions?

If an array of size n is rotated by d places, then the number of independent cycles will be gcd(n, d). When we rotate the array, the cycle increments in steps of d and terminates when we reach the starting point. This means that the distance travelled in each cycle will be a multiple of n, which is defined as lcm(n, d). So, number of elements in each cycle = lcm(n, d)/d. Therefore, to cover all n elements, the total number of cycles will be n*d/lcm(n, d) = gcd(n, d).

Below is the implementation of the algorithm:

C++

// C++ Program to left rotate the array by d positions // using Juggling Algorithm #include <bits/stdc++.h> using namespace std; // Function to rotate vector void rotateArr(vector<int> &arr, int d) {  int n = arr.size();  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  int cycles = __gcd(n, d);  // Process each cycle  for (int i = 0; i < cycles; i++) {   // Start element of current cycle  int startEle = arr[i];    // Start index of current cycle  int currIdx = i, nextIdx;    // Rotate elements till we reach the start of cycle  while(true) {  nextIdx = (currIdx + d) % n;    if(nextIdx == i)  break;    // Update the next index with the current element  arr[currIdx] = arr[nextIdx];  currIdx = nextIdx;  }    // Copy the start element of current cycle at the last  // index of the cycle  arr[currIdx] = startEle;  } } int main() {  vector<int> arr = {1, 2, 3, 4, 5, 6};  int d = 2;  rotateArr(arr, d);  // Print the rotated array  for (int i = 0; i < arr.size(); i++)  cout << arr[i] << " ";  return 0; }

// C Program to left rotate the array by d positions // using Juggling Algorithm #include <stdio.h> #include <stdlib.h> // Function to compute GCD int gcd(int a, int b) {  while (b != 0) {  int temp = b;  b = a % b;  a = temp;  }  return a; } // Function to rotate array void rotateArr(int arr[], int n, int d) {    // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  int cycles = gcd(n, d);  // Process each cycle  for (int i = 0; i < cycles; i++) {    // Start element of current cycle  int startEle = arr[i];    // Start index of current cycle  int currIdx = i, nextIdx;    // Rotate elements till we reach the start of cycle  while (1) {  nextIdx = (currIdx + d) % n;    if (nextIdx == i)  break;    // Update the next index with the current element  arr[currIdx] = arr[nextIdx];  currIdx = nextIdx;  }    // Copy the start element of current cycle at the last index of the cycle  arr[currIdx] = startEle;  } } int main() {  int arr[] = {1, 2, 3, 4, 5, 6};  int n = sizeof(arr) / sizeof(arr[0]);  int d = 2;  rotateArr(arr, n, d);  // Print the rotated array  for (int i = 0; i < n; i++)  printf("%d ", arr[i]);  return 0; }

Java

// Java Program to left rotate the array by d positions // using Juggling Algorithm import java.util.Arrays; class GfG {    // Function to rotate array  static void rotateArr(int[] arr, int d) {  int n = arr.length;  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  int cycles = gcd(n, d);  // Process each cycle  for (int i = 0; i < cycles; i++) {    // Start element of current cycle  int startEle = arr[i];    // Start index of current cycle  int currIdx = i, nextIdx;    // Rotate elements till we reach the start of cycle  while (true) {  nextIdx = (currIdx + d) % n;    if (nextIdx == i)  break;    // Update the next index with the current element  arr[currIdx] = arr[nextIdx];  currIdx = nextIdx;  }    // Copy the start element of current cycle at the last  // index of the cycle  arr[currIdx] = startEle;  }  }  // function to compute GCD  static int gcd(int a, int b) {  while (b != 0) {  int temp = b;  b = a % b;  a = temp;  }  return a;  }  public static void main(String[] args) {  int[] arr = {1, 2, 3, 4, 5, 6};  int d = 2;  rotateArr(arr, d);  // Print the rotated array  for (int i = 0; i < arr.length; i++)  System.out.print(arr[i] + " ");  } }

Python

# Python Program to left rotate the array by d positions # using Juggling Algorithm import math # Function to rotate array def rotateArr(arr, d): n = len(arr) # Handle the case where d > size of array d %= n # Calculate the number of cycles in the rotation cycles = math.gcd(n, d) # Process each cycle for i in range(cycles): # Start element of current cycle startEle = arr[i] # Start index of current cycle currIdx = i # Rotate elements till we reach the start of cycle while True: nextIdx = (currIdx + d) % n if nextIdx == i: break # Update the next index with the current element arr[currIdx] = arr[nextIdx] currIdx = nextIdx # Copy the start element of current cycle at the last # index of the cycle arr[currIdx] = startEle if __name__ == "__main__": arr = [1, 2, 3, 4, 5, 6] d = 2 rotateArr(arr, d) # Print the rotated array for i in range(len(arr)): print(arr[i], end=" ")

// C# Program to left rotate the array by d positions // using Juggling Algorithm using System; class GfG {    // Function to rotate array  static void rotateArr(int[] arr, int d) {  int n = arr.Length;  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  int cycles = gcd(n, d);  // Process each cycle  for (int i = 0; i < cycles; i++) {    // Start element of current cycle  int startEle = arr[i];    // Start index of current cycle  int currIdx = i, nextIdx;  // Rotate elements till we reach the start of cycle  while (true) {  nextIdx = (currIdx + d) % n;  if (nextIdx == i)  break;    // Update the next index with the current element  arr[currIdx] = arr[nextIdx];  currIdx = nextIdx;  }    // Copy the start element of current cycle at the last  // index of the cycle  arr[currIdx] = startEle;  }  }  // function to compute GCD  static int gcd(int a, int b) {  while (b != 0) {  int temp = b;  b = a % b;  a = temp;  }  return a;  }  static void Main(string[] args) {  int[] arr = { 1, 2, 3, 4, 5, 6 };  int d = 2;  rotateArr(arr, d);  // Print the rotated array  for (int i = 0; i < arr.Length; i++)  Console.Write(arr[i] + " ");  } }

JavaScript

// JavaScript Program to left rotate the array by d positions // using Juggling Algorithm // Function to rotate array function rotateArr(arr, d) {  let n = arr.length;  // Handle the case where d > size of array  d %= n;  // Calculate the number of cycles in the rotation  let cycles = gcd(n, d);  // Process each cycle  for (let i = 0; i < cycles; i++) {    // Start element of current cycle  let startEle = arr[i];    // Start index of current cycle  let currIdx = i, nextIdx;    // Rotate elements till we reach the start of cycle  while (true) {  nextIdx = (currIdx + d) % n;    if (nextIdx === i)  break;    // Update the next index with the current element  arr[currIdx] = arr[nextIdx];  currIdx = nextIdx;  }    // Copy the start element of current cycle at the last  // index of the cycle  arr[currIdx] = startEle;  } } // Helper function to compute GCD function gcd(a, b) {  while (b !== 0) {  let temp = b;  b = a % b;  a = temp;  }  return a; } let arr = [1, 2, 3, 4, 5, 6]; let d = 2; rotateArr(arr, d); // Print the rotated array console.log(arr.join(" "));