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