Reversal Algorithm for the Right Rotation of an Array in C++

Hello Folks, In this tutorial we are going to learn about the reversal algorithm for the right rotation of an array in C++. First, we will understand what do we mean by the right rotation of an array. So, the right rotation of an array means rotation of an array in the closed cycle in the right direction or the clockwise direction.

Let us consider an example;

int arr[10] = {1 2 3 4 5 6 7 8 9 10};
So after right rotation by k amount(say 2);
Roatated array will be;
arr[10] = {9 10 1 2 3 4 5 6 7 8};

Although there are many algorithms to implement this yet we will only discuss the reversal algorithm in this tutorial.

Reversal Algorithm for the Right Rotation of an Array and its Implementation in C++

Algorithm

  • First, we will reverse the whole array.
  • Then we will reverse the subarray from indices 0 to k-1, where k is the rotating amount.
  • Finally, we will reverse the subarray from indices k to n-1, where n is the size of the array.

Example;

arr[10] = {1 2 3 4 5 6 7 8 9 10};
k = 6;
// After First Step
arr[10] = {10 9 8 7 6 5 4 3 2 1};
// After Second Step
arr[10] = {5 6 7 8 9 10 4 3 2 1};
// After Last step 
// Roatated array
arr[10] = {5 6 7 8 9 10 1 2 3 4};

In this way, we will get the rotated array. Now, let us see the Implementation of the following Algorithm in C++.

Code

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

int main()
{
    // Given Array
    int arr[10] = {1,2,3,4,5,6,7,8,9,10};
    // size of the array arr
    int n = sizeof(arr)/sizeof(arr[0]);
    
    // Printing the original array
    cout<<"Given Array - \n";
    for(auto i: arr){
        cout<<i<<" ";
    }
    cout<<"\n";

    // Amount of the rotation as input
    int k;
    cin>>k;

    // Reverse whole array
    reverse(arr,arr+n);
    // Reverse subarray arr[0 to k-1]
    reverse(arr,arr+k);
    // Reverse subarray arr[k to n-1]
    reverse(arr+k,arr+n);

    // Rotated array
    cout<<"Array after rotation - \n";
    for(auto i: arr){
        cout<<i<<" ";
    }
    cout<<"\n";

    return 0;
}

Inputs

1
2
6

Outputs

Given Array - 
1 2 3 4 5 6 7 8 9 10 
Array after rotation -
10 1 2 3 4 5 6 7 8 9 

Given Array -
1 2 3 4 5 6 7 8 9 10
Array after rotation -
9 10 1 2 3 4 5 6 7 8

Given Array -
1 2 3 4 5 6 7 8 9 10
Array after rotation -
5 6 7 8 9 10 1 2 3 4

Time Complexity – O(n)
Space Complexity – O(1)

This is it for this tutorial.
Hope you like it.

Also Read:

  1. Kaprekar number in C++
  2. Count the Number of Divisors of n occurring within n in C++

Leave a Reply

Your email address will not be published. Required fields are marked *