Program to Cyclically Rotate an Array by k Positions

Cyclically Rotate an Array by K

 

Here, in this page we will discuss the program for cyclically rotate an array by k positions. We are given with an integer array and value of k, and need to print the array after cyclically rotate it by k positions.

Cyclically Rotate an Array by K

Method Discussed :

  • Method 1 : Using Temporary Array.
  • Method 2 : By rotating elements one by one.
  • Method 3 : By Using the reversing Concept.
  • Method 3 : Using juggling algorithm

Let’s discuss all the above methods one by one in brief,

Method 1 :

In this method we will declare an extra array to store some k elements. Here, k refers to number of rotations.

  • Declare a temporary array of size k.
  • Store the first k elements in temp[] array.
  • Now, shift the remaining elements.
  • After, shifting the elements add the elements of temp[] in the array
//Write a program to cyclically rotate an array by k
#include  <stdio.h>
 
/* Driver program to test above functions */
int main()
{
    int arr[] = { 10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;
    
    int temp_arr[k];
    for(int i=0; i<k; i++)
      temp_arr[i] = arr[i];
    
    int x = k;
    for(int i=0; x < n; i++){
        arr[i] = arr[x++];
    }
    x = 0;
    
    for(int i=n-k; i<n; i++)
       arr[i] = temp_arr[x++];
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
//Write a program to cyclically rotate an array by k
#include <bits/stdc++.h>
using namespace std;
 
/* Driver program to test above functions */
int main()
{
    int arr[] = { 10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;
    
    int temp_arr[k];
    for(int i=0; i<k; i++)
      temp_arr[i] = arr[i];
    
    int x = k;
    for(int i=0; x < n; i++){
        arr[i] = arr[x++];
    }
    x = 0;
    
    for(int i=n-k; i<n; i++)
       arr[i] = temp_arr[x++];
    for (int i = 0; i < n; i++)
        cout<< arr[i]<<" ";

    return 0;
}
class Main {

    public static void main(String[] args)
    {
        int arr[] = { 10, 20, 30, 40, 50, 60, 70};
        int n = arr.length;
        int k = 4;
        
        int[] temp;
         
        temp =  new int[n];
        
        for(int i=0; i< k; i++)
            temp[i] = arr[i];
    
        int x = k;
        for(int i=0; x < n; i++){
            arr[i] = arr[x++];
        }
        
        x = 0;
    
        for(int i=n-k; i<n; i++)
            arr[i] = temp[x++];
    
   
        for (int i = 0; i < 7; i++)
            System.out.print(arr[i] + " ");
    }
}

Output

50 60 70 10 20 30 40

Method 2 :

In this method we cyclically rotate the array by shifting elements one by one.

//Write a program to cyclically rotate an array by k
#include <stdio.h>
 
void cyclicRotatebyOne(int arr[], int n)
{
    int temp = arr[0], i;
    for (i = 0; i < n - 1; i++)
        arr[i] = arr[i + 1];
    arr[n-1] = temp;
}

void cyclicRotate(int arr[], int k, int n)
{
    for (int i = 0; i < k; i++)
        cyclicRotatebyOne(arr, n);
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = { 10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;
    
    cyclicRotate(arr, k, n);
    
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
//Write a program to cyclically rotate an array by k
#include <iostream>
using namespace std;
 
void cyclicRotatebyOne(int arr[], int n)
{
    int temp = arr[0], i;
    for (i = 0; i < n - 1; i++)
        arr[i] = arr[i + 1];
    arr[n-1] = temp;
}

void cyclicRotate(int arr[], int k, int n)
{
    for (int i = 0; i < k; i++)
        cyclicRotatebyOne(arr, n);
}
 
/* Driver program to test above functions */
int main()
{
    int arr[] = { 10, 20, 30, 40, 50, 60, 70};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 4;
    
    cyclicRotate(arr, k, n);
    
    for (int i = 0; i < n; i++)
        cout<< arr[i]<<" ";

    return 0;
}
#Write a program for array rotation in Python

# Python3 program to rotate an array by
def leftRotate(arr, d, n):
    for i in range(d):
        leftRotatebyOne(arr, n)
 
# Function to left Rotate arr[] of size n by 1*/
def leftRotatebyOne(arr, n):
    temp = arr[0]
    for i in range(n-1):
        arr[i] = arr[i + 1]
    arr[n-1] = temp
         
 
# utility function to print an array */
def printArray(arr, size):
    for i in range(size):
        print ("% d"% arr[i], end =" ")
 
  
# Driver program to test above functions */
arr = [10, 20, 30, 40, 50, 60, 70]
leftRotate(arr, 4, 7)
printArray(arr, 7)
class Main {

    public static void main(String[] args)
    {
        int arr[] = { 10, 20, 30, 40, 50, 60, 70};
        int n = arr.length;
        int k = 4;
        
        int[] temp;
         
        temp =  new int[n];
        
        for(int i=0; i<k; i++)
            temp[i] = arr[i];
    
        int x = k;
        for(int i=0; x < n; i++){
            arr[i] = arr[x++];
        }
        
        x = 0;
    
        for(int i=n-k; i<n; i++)
            arr[i] = temp[x++];
    
   
        for (int i = 0; i < 7; i++)
            System.out.print(arr[i] + " ");
    }
}

Output

50 60 70 10 20 30 40

Method 3 :

  • Set K to points that element which comes at first position, i.e. K = N-K.
  • Reverse the array from 0 to K-1 position.
  • Again reverse the array from K to N-1 position.
  • And then finally reverse the entire array.
  • Doing so we will get the desired circularly rotated array by K position.
//Write a program to cyclically rotate an array by k
#include <bits/stdc++.h>
using namespace std;
 
/* Driver program to test above functions */
int main()
{
    std::vector<int>arr= { 10, 20, 30, 40, 50, 60, 70};
    int n = arr.size();
    int k = 3;
    k = n-k;
    
    reverse(arr.begin(), arr.begin()+k);
    reverse(arr.begin()+k, arr.end());
    reverse(arr.begin(), arr.end());
    
    
    for (int i = 0; i < n; i++)
        cout<< arr[i]<<" ";

    return 0;
}

Output

50 60 70 10 20 30 40

Method 4 :

In this method we will use the concept of juggling algorithm for cyclically rotate the array by K positions.

You can check out the page for understanding it’s algorithm.

//Write a program to cyclically rotate an array by k
#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
void ArrayRotate(int A[], int n, int k) {
    int d = -1, i, temp, j;
    for (i = 0; i < gcd(n, k); i++) {
        j = i;
        temp = A[i];
        while (1) {
            d = (j + k) % n;
            if (d == i) break;
            A[j] = A[d];
            j = d;
        }
        A[j] = temp;
    }
}
void displayArray(int A[], int n) {
    int i;
    for (i = 0; i < n; i++) 
    printf("%d ", A[i]);
}
int main() {
    int n = 7, i, k = 4;
    int A[7] = {10, 20, 30, 40, 50, 60, 70};

    ArrayRotate(A, n, k);
    displayArray(A, n);
    return 0;
}

//Write a program to cyclically rotate an array by k

#include <bits/stdc++.h>
using namespace std;
 int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
void ArrayRotate(int A[], int n, int k) {
    int d = -1, i, temp, j;
    for (i = 0; i < gcd(n, k); i++) {
        j = i;
        temp = A[i];
        while (1) {
            d = (j + k) % n;
            if (d == i) break;
            A[j] = A[d];
            j = d;
        }
        A[j] = temp;
    }
}
void displayArray(int A[], int n) {
    int i;
    for (i = 0; i < n; i++) 
    cout<<A[i]<<" ";
}
int main() {
    int n = 7, i, k = 4;
    int A[n] = {10, 20, 30, 40, 50, 60, 70};

    ArrayRotate(A, n, k);
    displayArray(A, n);
    return 0;
}

//Write a program to cyclically rotate an array by k
public class Main
{
       public static int hcf(int a, int c) 
    { 
        if (c == 0) 
             return a; 
        else
             return hcf(c, a % c); 
    }
    
    //Function to left rotate array of by d number of rotations
    public static void leftRotate(int arr[], int d, int n) 
    { 
        int i, l, m, temp; 
        for (i = 0; i < hcf(d, n); i++)  // hcf(d,n) times the loop will iterate 
        { 
             // move i-th values of blocks 
            temp = arr[i]; 
            l = i; 
            while (true) { 
                m = l + d; 
                if (m >= n)  // The element has to be shifted to its rotated position
                    m = m - n; 
                if (m == i)  // The element is already in its rotated position
                    break; 
                arr[l] = arr[m]; 
                l = m; 
            } 
            arr[l] = temp; 
        }
        
    } 
    
    //  Main function
    public static void main(String[] args) 
    { 
        int arr[] = { 10, 20, 30, 40, 50, 60, 70 }; 
        int no_of_rotation = 4;
        int n = arr.length;
        
        leftRotate(arr, no_of_rotation, n); 
        
        for(int i = 0 ; i < n ; i++)
        {
            System.out.print(arr[i] +  " "); 
        }
    }
 }

import math

def leftRotate(arr, d, n): 
     for i in range(math.gcd(d, n)): 
         temp = arr[i] 
         j = i 
         while 1: 
             k = j + d 
             if k >= n:
                 k = k - n 
             if k == i: 
                 break
             arr[j] = arr[k] 
             j = k 
             arr[j] = temp
             
arr =[10, 20, 30, 40, 50, 60, 70]
n = len(arr)
no_of_rotations = 4
leftRotate(arr, no_of_rotations, n )
print(*arr)

Output

50 60 70 10 20 30 40