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 3

LEFT ROTATION

This is an easy approach with a simpler code.

In this approach we run a loop from i=0 till i<n and print arr[(k+i)%n]  every time the loop executes.

%(modulo operator) gives the remainder.

For the array 1 2 3 4 5 when k=3 and

  • i=0, arr[(k+i)%n] i.e arr[3%5] will be equal to arr[3] which is equal to 4. So 4 will be printed first.
  • i=1, arr[(k+i)%n] i.e arr[4%5] will be equal to arr[4] which is equal to 5. So 5 will be printed next.
  • i=2, arr[(k+i)%n] i.e arr[5%5] will be equal to arr[0] which is equal to 1. So 1 will be printed next.
  • i=3, arr[(k+i)%n] i.e arr[6%5] will be equal to arr[1] which is equal to 2. So 2 will be printed next.
  • i=4, arr[(k+i)%n] i.e arr[7%5] will be equal to arr[2] which is equal to 3. So 3 will be printed next.
  • Now i becomes equal to n so the loop ends.
  • So 4 5 1 2 3 would be our output which is the required output for left rotation.

 

#include <iostream>
using namespace std;

//function to left rotate the array of size n by k times and print them
void left_rotate(int arr[],int n,int k)
{
    k=k%n;
    for(int i=0;i<n;i++)
    cout<<(arr[(k+i)%n])<<" ";
}

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);

    return 0;
}

 

RIGHT ROTATION

In right rotation we take k as n-k and then solve it in the same way as left rotation.

 

#include <iostream>
using namespace std;

//function to right rotate the array of size n by k times and print them
void right_rotate(int arr[],int n,int k)
{
    k=k%n;
    k=n-k;
    for(int i=0;i<n;i++)
    cout<<(arr[(k+i)%n])<<" ";
}

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);

    return 0;
}

 

TIME COMPLEXITY

The time complexity for this approach is O(n).

Discussion

19