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 1 (ROTATING ONE BY ONE)

LEFT ROTATION

In this approach, we store the element at index zero i.e arr[0] in a temporary variable say temp and shift arr[1] to arr[0], arr[2] to arr[1], arr[3] to arr[2], ....... , arr[n-1] to arr[n-2] (n is the size of the array) and finally we put temp in arr[n-1].We do this k times where k is the number of times we need to left rotate the array before printing it.

 

#include <bits/stdc++.h>
using namespace std;

//this function left rotates the array of size n by k times
void left_rotate(int arr[],int n,int k)
{
    for(int i=0;i<k;i++)
    {
        int temp=arr[0];
        for(int j=0;j<n-1;j++)
        {
            arr[j]=arr[j+1];
        }
        arr[n-1]=temp;
    }
}

//this function prints 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);   //function to left rotate the array by k times
    print_array(arr,n);    //function to print the array elements

    return 0;
}

For the input :

 5 3

1 2 3 4 5

The output will be

4 5 1 2 3

 

RIGHT ROTATION

In this approach, we store the element at the last index i.e arr[n-1] in a temporary variable say temp and shift arr[n-2] to arr[n-1], arr[n-3] to arr[n-2], ....... , arr[1] to arr[2] , arr[0] to arr[1] (n is the size of the array) and finally we put temp in arr[0].We do this k times where k is the number of times we need to right rotate the array before printing it.

 

#include <bits/stdc++.h>
using namespace std;

//this function right rotates the array of size n by k times
void right_rotate(int arr[],int n,int k)
{
    for(int i=0;i<k;i++)
    {
        int temp=arr[n-1];
        for(int j=n-1;j>0;j--)
        {
            arr[j]=arr[j-1];
        }
        arr[0]=temp;
    }
}

//this function prints 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);      //function to right rotate the array by k times 
    print_array(arr,n);          //function to print the array elements

    return 0;
}

For the input:

5 3

1 2 3 4 5

The output will be 

3 4 5 1 2

TIME COMPLEXITY

The time complexity for this approach is O(n*k) where n is the size of the array and k is the number of times we have to rotate the array.

Discussion

19