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 LEFT ROTATION)

LEFT ROTATION

In this approach we divide the array into two parts, the first part is from arr[0] to arr[k-1] ,the second part is from k to 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[2] i.e from element 1 to 3.
  • If we reverse the first part, our array will look like this

                                         3 2 1 4 5

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

                                         3 2 1 5 4

  • So now our array is 3 2 1 5 4. Upon reversing the entire array we get 4 5 1 2 3 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 left rotate the array of size n by k times
void left_rotate(int arr[],int n,int k)
{
    if(k==0)
    return;
    
    k=k%n;
    
    reverse(arr,0,k-1);
    reverse(arr,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];
    left_rotate(arr,n,k);
    print_array(arr,n);

    return 0;
}

 

We do k=k%n inorder to deal with cases where k is greater than n.

Discussion

19