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:
Leave a Reply