Example:
Array = {1, 2, 3, 4, 5 ,6, 7};
n = 4
Output:
[4, 5, 6, 7, 1, 2, 3]
Explanation:
rotate 1 steps to the right: [7, 1, 2, 3, 4, 5, 6]
rotate 2 steps to the right: [6, 7, 1, 2, 3, 4, 5]
rotate 3 steps to the right: [5, 6, 7, 1, 2, 3, 4]
rotate 4 steps to the right: [4, 5, 6, 7, 1, 2, 3]
This problem can be solved in 2 different ways.
Method 1: Take the copy of the array and rotate the elements.
In this solution we take a copy of the array then, we replace the items based on the formula “(i + k)%len”.
This will start from the position to be rotated. Then copy the elements from the copy array to the original array.
Test Case: K = 4, hence the position will become i = 0 k = 4 len = 7 (i + k)%len = 4 i = 1 k = 4 len = 7 (i + k)%len = 5 i = 2 k = 4 len = 7 (i + k)%len = 6 i = 3 k = 4 len = 7 (i + k)%len = 0 i = 4 k = 4 len = 7 (i + k)%len = 1 i = 5 k = 4 len = 7 (i + k)%len = 2 i = 6 k = 4 len = 7 (i + k)%len = 3
Method 2: By reversing the array 3 times.
Reverse 1: Reverse the whole array
Reverse 2: Reverse the elements from 0 to k.
Reverse 3: Reverse from k to n.
Solution in C++
#include<iostream>
#include<vector>
using namespace std;
vector<int> rotate_method_1(vector<int> array, int k)
{
int len = array.size();
//take the copy of the array
vector<int> array_copy(len);
for (int i = 0; i < len; i++)
{
array_copy[i] = array[i];
}
// Rotate the elements.
for (int i = 0; i < len; i++)
{
array[(i + k)%len] = array_copy[i];
}
return array;
}
vector<int> rotate_method_2(vector<int> array, int k)
{
int len = array.size();
reverse(array.begin(), array.end());
reverse(array.begin(), array.begin()+k%len);
reverse(array.begin()+k%len, array.begin()+len);
return array;
}
int main()
{
std::vector<int> array = {1, 2, 3, 4, 5, 6, 7};
int k = 4;
cout<<"Before Rotation "<<endl;
for (int i = 0; i < array.size(); i++)
{
cout <<array[i] << " ";
}
cout<<"\n\nAfter Rotation using method 1:"<<endl;
vector<int> result = rotate_method_1(array, k);
for (int i = 0; i < result.size(); i++)
{
cout <<result[i] << " ";
}
cout<<endl;
cout<<"\n\nAfter Rotation using method 2:"<<endl;
result = rotate_method_2(array, k);
for (int i = 0; i < result.size(); i++)
{
cout <<result[i] << " ";
}
cout<<endl;
return 0;
}
Output:
Before Rotation 1 2 3 4 5 6 7 After Rotation using method 1: 4 5 6 7 1 2 3 After Rotation using method 2: 4 5 6 7 1 2 3
