Question:
Given an arrays, rotate it one time cyclically
Example:
Input :
arr = {1, 2, 3, 4, 5, 6, 7, 8}
Output:
rotating it one time will become {8, 1, 2, 3, 4, 5, 6, 7}
We can modify the question, to rotate the array “k” times.
We can solve this question by multiple methods. Some of them are:
1. Rotating the array k times
2. By taking temp array
3. By reversing the array
1. Rotating the array k times
1. Create a function to rotate an array one time.
2. Call that function k times.
To create a function to rotate an array one time, follow below steps:
1. Store the last element of that array in a temp variable.
2. Shift all the elements by one position
3. Replace the first element of the array with the temp variable.
The time complexity is O(n*k).
How?
To rotate the full array it will take O(n) time
We need to rotate the array k times, hence O(n*k)
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <queue>
using namespace std;
void rotate_once(int arr[], int size)
{
int temp = arr[size - 1];
int i;
for (i = size - 1; i >= 0; i--)
arr[i + 1] = arr[i];
arr[0] = temp;
}
void rotate_k_times(int arr[], int size, int k)
{
for (int i = 0; i < k; i++)
{
rotate_once(arr, size);
}
}
int main(void)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int k = 3;
int size = sizeof(arr)/sizeof(arr[0]);
cout<<"Before rotation \n";
for (int i = 0; i < size; i++)
cout<< arr[i]<< " ";
cout<<endl;
rotate_k_times(arr, size, k);
cout<<"After rotation \n";
for (int i = 0; i < size; i++)
cout<< arr[i]<< " ";
cout<<endl;
return 0;
}
Output:
Before rotation
1 2 3 4 5 6 7
After rotation
5 6 7 1 2 3 4
2. By taking temp array
The idea here is to take a temp array.
Copy the last “k” elements in to an temp array.
Shift n-k elements of the input array to the end.
Copy the temp array elements to their correct positions.
The time complexity is O(n) and space complexity is O(k).
We shall look at it with the help of an example:
Consider the array:
arr = { 1, 2, 3, 4, 5, 6, 7 };
k = 3.
In the first step is to copy the last “k” elements into the temp array:
temp_arr = { 5, 6, 7}
Shift n-k elements to the end of the array:
orig_array = { 1, 2, 3, 1, 2, 3, 4 }
Put the elements in temp_array in the beginning of the orig_array
orig_array = { 5, 6, 7, 1, 2, 3, 4 }
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <queue>
using namespace std;
void rotate_k_times(int arr[], int k, int size)
{
// copy the last k element of the array
// in to the temp_array
int temp_arr[k];
for (int i = 0; i < k; i++)
temp_arr[i] = arr[size-k+i];
// shift the elements in the orig array to the end
for (int i = size-k-1; i >= 0; i--)
arr[i+k] = arr[i];
// copy the elements of temp_arr to orig array
for (int i = 0; i < k; i++)
arr[i] = temp_arr[i];
}
int main(void)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int k = 3;
int size = sizeof(arr)/sizeof(arr[0]);
rotate_k_times(arr, k, size);
for (int i = 0; i < size; i++)
cout<< arr[i]<< " ";
cout<<endl;
return 0;
}
Output
5 6 7 1 2 3 4
3. By reversing the array
We can solve this be using below steps:
1. Reverse the last k elements
2. Reverse the remaining n-k elements
3. Reverse the whole array.
The time complexity is O(n) and space complexity is O(1)
We can understand with the help of example:
Orig_array = { 1, 2, 3, 4, 5, 6, 7}
1. Reverse the last k elements:
1 2 3 4 7 6 5
2. Reverse the remaining n-k elements:
4 3 2 1 7 6 5
3. Reverse the whole array:
5 6 7 1 2 3 4
Solution in C++
#include <vector>
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <queue>
using namespace std;
void reverse(int arr[], int low, int high)
{
for (int i = low, j = high; i < j; i++, j--)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
void rotate_k_times(int arr[], int k, int size)
{
// reverse last 'k' elements
reverse(arr, size-k, size-1);
// reverse first 'n-k' elements
reverse(arr, 0, size-k-1);
// reverse whole array
reverse(arr, 0, size-1);
}
int main(void)
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
int k = 3;
int n = sizeof(arr)/sizeof(arr[0]);
rotate_k_times(arr, k, n);
for (int i = 0; i < n; i++)
cout<< arr[i]<<" ";
cout<<endl;
return 0;
}
Output:
5 6 7 1 2 3 4