Hello Everyone,
Given an array of size n and multiple values around which we need to left rotate the array. How to quickly print multiple left rotations?
Examples :
Input : arr[] = {1, 3, 5, 7, 9} k1 = 1 k2 = 3 k3 = 4 k4 = 6 Output : 3 5 7 9 1 7 9 1 3 5 9 1 3 5 7 3 5 7 9 1 Input : arr[] = {1, 3, 5, 7, 9} k1 = 14 Output : 9 1 3 5 7
We have discussed a solution in the below post.
[ Quickly find multiple left rotations of an array ]
The solution discussed above requires extra space. In this post, an optimized solution is discussed that doesn’t require extra space.
- C++
// C++ implementation of left rotation of
// an array K number of times
#include <bits/stdc++.h>
using namespace std;
// Function to leftRotate array multiple times
void leftRotate( int arr[], int n, int k)
{
/* To get the starting point of rotated array */
int mod = k % n;
// Prints the rotated array from start position
for ( int i = 0; i < n; i++)
cout << (arr[(mod + i) % n]) << " " ;
cout << "\n" ;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 7, 9 };
int n = sizeof (arr) / sizeof (arr[0]);
int k = 2;
// Function Call
leftRotate(arr, n, k);
k = 3;
// Function Call
leftRotate(arr, n, k);
k = 4;
// Function Call
leftRotate(arr, n, k);
return 0;
}
Output
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7
Method II:
In the below implementation we will use Standard Template Library (STL) which will be making the solution more optimize and easy to Implement.
- C++
- Java
- Python3
// C++ Implementation For Print Left Rotation Of Any Array K
// Times
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// Function For The k Times Left Rotation
void leftRotate( int arr[], int k, int n)
{
// Stl function rotates takes three parameters - the
// beginning,the position by which it should be rotated
// ,the end address of the array
// The below function will be rotating the array left
// in linear time (k%arraySize) times
rotate(arr, arr + (k % n), arr + n);
// Print the rotated array from start position
for ( int i = 0; i < n; i++)
cout << arr[i] << " " ;
cout << "\n" ;
}
// Driver program
int main()
{
int arr[] = { 1, 3, 5, 7, 9 };
int n = sizeof (arr) / sizeof (arr[0]);
int k = 2;
// Function Call
leftRotate(arr, k, n);
return 0;
}
Output
5 7 9 1 3
Note: the array itself gets updated after the rotation.