ARRAY ROTATION

ARRAY ROTATION

This is a beginner level lab that deals with various approaches to solve questions related to array rotations.

 

WHAT WILL YOU LEARN:

  • Left rotation of arrays
  • Right rotation of arrays
  • Various approaches to rotate arrays along with their time complexities

 

PRE-REQUISITES:

Basic knowledge of arrays and C++.

 

Lets get started

 

APPROACH 2 (REVERSAL ALGORITHM FOR RIGHT ROTATION)

RIGHT ROTATION

For right rotation also we divide the array into two parts but here the first part is from arr[0] to arr[n-k-1] , the second part is from arr[n-k] to arr[n-1]. We reverse both the parts of the array and then reverse the entire array to get the desired output.

  • Lets say the array is 1 2 3 4 5 and k is 3.
  • The first part is from arr[0] to arr[1] i.e from element 1 to 2.
  • If we reverse the first part, our array will look like this

                                         2 1 3 4 5

  • The second part of the array is from arr[2] to arr[4] i.e from element 3 to 5.
  • If we reverse the second part, our array will look like this

                                         2 1 5 4 3

  • So now our array is 2 1 5 4 3. Upon reversing the entire array we get 3 4 5 1 2 which is the desired output.

 

#include <iostream>
using namespace std;

//function to reverse the array from start to end 
void reverse(int arr[],int start,int end)
{
    while(start<end)
    {
        int temp=arr[start];
        arr[start]=arr[end];
        arr[end]=temp;
        start++;
        end--;
    }
}

//function to right rotate the array of size n by k times
void right_rotate(int arr[],int n,int k)
{
    if(k==0)
    return;
    
    k=k%n;
    
    reverse(arr,0,n-k-1);
    reverse(arr,n-k,n-1);
    reverse(arr,0,n-1);
}

//function to print all the elements of the array
void print_array(int arr[],int n)
{
   for(int i=0;i<n;i++)
   cout<<arr[i]<<" ";
}

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++)
    cin>>arr[i];
    right_rotate(arr,n,k);
    print_array(arr,n);

    return 0;
}

 

TIME COMPLEXITY

The time complexity for this approach is O(n)

Discussion

19