Juggling algorithm for array rotation | Faceprep

10 min read

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[0]); // 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


juggling algorithm for array rotation



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 Function
import array as arr
arr = arr.array('i', [1,2,3,4,5,6,7])
n = len(arr)
no_of_rotations = 2

print("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 = ' ')
POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error