Rotate array is a problem in which we have given an array of size N. We have to rotate the array in the right direction. Each element shift by one position right and last element of the array come to the first position. So, we have given a value K and we have to shift the array K times towards right and then print the final array. Let’s see how to rotate the array by shifting all elements toward the right by taking an example.
Table of Contents
Input Format
First line containing two integer values N and K denoting the number of elements in the input array and number of right shifts perform on a given array.
The second line containing an input array which have N integer values.
Output Format
The first line containing the final array after performing K right shift.
Constraints
- 1<=N<=100000
- -10^9<=A[i]<=10^9
- 1<=k<=10^9
8 4 1 5 9 6 5 4 2 7
2 7 1 5 9 6 5 4
Explanation
In the given array first, we reverse all the array. After it reverses the array from beginning to (K%N-1). After this, we swap the last remaining elements and got the final array which comes after K right shift.
Algorithm For Rotate Array
Step:1 Reverse all the array. Step:2 Reverse first K%N elements. Step:3 Reverse last N-K%N elements. Step:4 Print the final array.
Implementation For Rotate Array
/*C++ Implementation of Rotate Array.*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
/*input values.*/
int n,k;
cin>>n>>k;
vector<int> a;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
a.push_back(x);
}
reverse(a.begin(),a.end());
reverse(a.begin(),a.begin()+k%n);
reverse(a.begin()+k%n,a.end());
for(int i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}13 17 1 6 24 65 13 -234 0 12 54 3 -1 6 3
3 -1 6 3 1 6 24 65 13 -234 0 12 54
Time Complexity
O(N) where N is the size of the input array. Here we use the reverse function which takes linear time to reverse the number. Here maximum we reverse all the input array. So, our maximum time complexity will be O(N).
Space Complexity
O(1) because we don’t use any extra space here. We use the reverse function which takes O(1) space to reverse the number.