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 | Set 1
Method I: The solution discussed above requires extra space. In this post, an optimized solution is discussed that doesn’t require extra space.
Implementation:
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 timesvoid 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 Codeint 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;} |
C
#include <stdio.h>// Function to leftRotate array multiple timesvoid 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++) printf("%d ", arr[(mod + i) % n]); printf("\n");}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;} |
Java
// JAVA implementation of left rotation// of an array K number of timesimport java.util.*;import java.lang.*;import java.io.*;class arr_rot { // Function to leftRotate array multiple // times static 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) System.out.print(arr[(i + mod) % n] + " "); System.out.println(); } // Driver code public static void main(String[] args) { int arr[] = { 1, 3, 5, 7, 9 }; int n = arr.length; 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); }}// This code is contributed by Sanjal |
Python
# Python implementation of left rotation of# an array K number of times# Function to leftRotate array multiple timesdef leftRotate(arr, n, k): # To get the starting point of rotated array mod = k % n s = "" # Prints the rotated array from start position for i in range(n): print str(arr[(mod + i) % n]), print return# Driver codearr = [1, 3, 5, 7, 9]n = len(arr)k = 2# Function CallleftRotate(arr, n, k)k = 3# Function CallleftRotate(arr, n, k)k = 4# Function CallleftRotate(arr, n, k)# This code is contributed by Sachin Bisht |
C#
// C# implementation of left// rotation of an array K// number of timesusing System;class GFG { // Function to leftRotate // array multiple times static 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) Console.Write(arr[(i + mod) % n] + " "); Console.WriteLine(); } // Driver Code static public void Main() { int[] arr = { 1, 3, 5, 7, 9 }; int n = arr.Length; 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); }}// This code is contributed by m_kit |
Javascript
<script>// JavaScript implementation of left rotation of// an array K number of times// Function to leftRotate array multiple timesfunction leftRotate(arr, n, k){ /* To get the starting point of rotated array */ let mod = k % n; // Prints the rotated array from start position for (let i = 0; i < n; i++) document.write((arr[(mod + i) % n]) + " "); document.write("\n");}// Driver Codelet arr = [ 1, 3, 5, 7, 9 ];let n = arr.length;let k = 2;// Function CallleftRotate(arr, n, k);document.write("<br>");k = 3;// Function CallleftRotate(arr, n, k);document.write("<br>");k = 4;// Function CallleftRotate(arr, n, k);</script> |
PHP
<?php// PHP implementation of // left rotation of an// array K number of times// Function to leftRotate// array multiple timesfunction leftRotate($arr, $n, $k){ // To get the starting // point of rotated array $mod = $k % $n; // Prints the rotated array // from start position for ($i = 0; $i < $n; $i++) echo ($arr[($mod + $i) % $n]) , " "; echo "\n";}// Driver Code$arr = array(1, 3, 5, 7, 9);$n = sizeof($arr);$k = 2;// Function CallleftRotate($arr, $n, $k);$k = 3;// Function CallleftRotate($arr, $n, $k);$k = 4;// Function CallleftRotate($arr, $n, $k);// This code is contributed by m_kit?> |
Output
5 7 9 1 3 7 9 1 3 5 9 1 3 5 7
Time Complexity: O(N), as we are using a loop to traverse N times.
Auxiliary Space: O(1), as we are not using any extra space.
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.
Implementation:
C++
// 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 Rotationvoid 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 programint 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;} |
C
#include <stdio.h>// Function For k Times Left Rotationvoid leftRotate(int arr[], int k, int n){ int i, temp; // Perform k left rotations for (i = 0; i < k; i++) { // Store the first element of the array temp = arr[0]; // Shift all elements one position to the left for (int j = 0; j < n - 1; j++) { arr[j] = arr[j + 1]; } // Place the first element at the end arr[n - 1] = temp; } // Print the rotated array for (i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n");}// Driver programint 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;} |
Java
// Java implementation for print left // rotation of any array K timesimport java.io.*;import java.util.*;class GFG{ // Function for the k times left rotationstatic void leftRotate(Integer arr[], int k, int n){ // In Collection class rotate function // takes two parameters - the name of // array and the position by which it // should be rotated // The below function will be rotating // the array left in linear time // Collections.rotate()rotate the // array from right hence n-k Collections.rotate(Arrays.asList(arr), n - k); // Print the rotated array from start position for(int i = 0; i < n; i++) System.out.print(arr[i] + " ");}// Driver codepublic static void main(String[] args) { Integer arr[] = { 1, 3, 5, 7, 9 }; int n = arr.length; int k = 2; // Function call leftRotate(arr, k, n);}}// This code is contributed by chahattekwani71 |
Python3
# Python3 implementation to print left # rotation of any array K timesfrom collections import deque # Function For The k Times Left Rotationdef leftRotate(arr, k, n): # The collections module has deque class # which provides the rotate(), which is # inbuilt function to allow rotation arr = deque(arr) # using rotate() to left rotate by k arr.rotate(-k) arr = list(arr) # Print the rotated array from # start position for i in range(n): print(arr[i], end = " ")# Driver Codeif __name__ == '__main__': arr = [ 1, 3, 5, 7, 9 ] n = len(arr) k = 2 # Function Call leftRotate(arr, k, n)# This code is contributed by math_lover |
C#
// C# program for the above approachusing System;class GFG{ static void leftRotate(int[] arr, int d, int n) { for (int i = 0; i < d; i++) leftRotatebyOne(arr, n); } static void leftRotatebyOne(int[] arr, int n) { int i, temp = arr[0]; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[n - 1] = temp; } /* utility function to print an array */ static void printArray(int[] arr, int size) { for (int i = 0; i < size; i++) Console.Write(arr[i] + " "); }// Driver Codepublic static void Main(){ int[] arr = { 1, 3, 5, 7, 9 }; int n = arr.Length; int k = 2; // Function call leftRotate(arr, k, n); printArray(arr, n);}}// This code is contributed by avijitmondal1998. |
Javascript
<script>// Javascript program for the above approachfunction leftRotate(arr, d, n){ for (let i = 0; i < d; i++) leftRotatebyOne(arr, n);} function leftRotatebyOne(arr, n){ let i, temp = arr[0]; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[n - 1] = temp;} /* utility function to print an array */function printArray(arr, size){ for (let i = 0; i < size; i++) document.write(arr[i] + " ");}// Driver Codelet arr = [ 1, 3, 5, 7, 9 ];let n = arr.length;let k = 2; // Function callleftRotate(arr, k, n);printArray(arr, n);// This code is contributed by Samim Hossain Mondal.</script> |
Output
5 7 9 1 3
Note: the array itself gets updated after the rotation.
Time Complexity: O(n)
Auxiliary Space: O(1), since no extra space has been taken.
Method III(Using Reversal):
To left rotate an array by “k” units we will perform 3 simple reversals-
- Reverse the first “k” elements
- Reverse the last “n-k” elements where n is the size of the array
- Reverse the whole array
Code-
C++
// 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 Rotationvoid leftRotate(int arr[], int k, int n){ // if k>n , k%n will bring k back in range k = (k%n); reverse(arr,arr+k); reverse(arr+k,arr+n); reverse(arr,arr+n); // Print the rotated array from start position for (int i = 0; i < n; i++) cout << arr[i] << " "; cout << "\n";}// Driver programint 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;} |
C
#include <stdio.h>// Function For k Times Left Rotationvoid leftRotate(int arr[], int k, int n){ // if k > n, k % n will bring k back in range k = (k % n); // Reverse the first part of the array (0 to k-1) for (int i = 0, j = k - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Reverse the second part of the array (k to n-1) for (int i = k, j = n - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Reverse the entire array for (int i = 0, j = n - 1; i < j; i++, j--) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // Print the rotated array for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } printf("\n");}// Driver programint 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;} |
Java
import java.util.*;public class Main { // Function for k times left rotation public static void leftRotate(int[] arr, int k) { // if k>arr.length,k%arr.length will bring k back to range k%=arr.length; // Reverse the first k elements reverseArray(arr, 0, k - 1); // Reverse the remaining n-k elements reverseArray(arr, k, arr.length - 1); // Reverse the entire array reverseArray(arr, 0, arr.length - 1); // Print the rotated array from start position String result = Arrays.toString(arr).replaceAll("\\[|\\]|,|\\s", " "); System.out.println(result); } // Helper function to reverse a section of an array from start to end (inclusive) public static void reverseArray(int[] arr, int start, int end) { while (start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } // Driver code public static void main(String[] args) { int[] arr = {1, 3, 5, 7, 9}; int k = 2; // Function Call leftRotate(arr, k); }} |
Python3
# Function for k times left rotationdef leftRotate(arr, k): # if k>len(arr) , k%=len(arr) bring k back to range k%len(arr) # Reverse the first k elements arr = reverseArray(arr, 0, k - 1) # Reverse the remaining n-k elements arr = reverseArray(arr, k, len(arr) - 1) # Reverse the entire array arr = reverseArray(arr, 0, len(arr) - 1) # Print the rotated array from start position print(" ".join(map(str,arr)))# Helper function to reverse a section of an array from start to end (inclusive)def reverseArray(arr, start, end): while start < end: temp = arr[start] arr[start] = arr[end] arr[end] = temp start += 1 end -= 1 return arr# Driver codearr = [1, 3, 5, 7, 9]k = 2 # Function CallleftRotate(arr, k) |
C#
// C# Implementation For Print Left Rotation Of Any Array K// Timesusing System;using System.Collections.Generic;class Program { // Driver program static void Main(string[] args) { int[] arr = { 1, 3, 5, 7, 9 }; int n = arr.Length; int k = 2; leftRotate(arr, k, n); Console.ReadKey(); } // Function For The k Times Left Rotation static void leftRotate(int[] arr, int k, int n) { k%=n; Array.Reverse(arr, 0, k); Array.Reverse(arr, k, n - k); Array.Reverse(arr, 0, n); // Print the rotated array from start position for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); Console.WriteLine(); }}// This code is contributed by Tapesh(tapeshdua420) |
Javascript
// Function for k times left rotationfunction leftRotate(arr, k) { k%=arr.length // Reverse the first k elements arr = reverseArray(arr, 0, k - 1); // Reverse the remaining n-k elements arr = reverseArray(arr, k, arr.length - 1); // Reverse the entire array arr = reverseArray(arr, 0, arr.length - 1); // Print the rotated array from start position console.log(arr.join(" "));}// Helper function to reverse a section of an array from start to end (inclusive)function reverseArray(arr, start, end) { while (start < end) { let temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } return arr;}// Driver codelet arr = [1, 3, 5, 7, 9 ];let n = arr.length;let k = 2; // Function CallleftRotate(arr, k, n); |
Kotlin
fun leftRotate(arr: IntArray, k: Int, n: Int) { // If k > n, k % n will bring k back in range val rotation = k % n // Reverse the first part of the array (0 to rotation-1) for (i in 0 until rotation / 2) { val temp = arr[i] arr[i] = arr[rotation - i - 1] arr[rotation - i - 1] = temp } // Reverse the second part of the array (rotation to n-1) for (i in 0 until (n - rotation) / 2) { val temp = arr[rotation + i] arr[rotation + i] = arr[n - i - 1] arr[n - i - 1] = temp } // Reverse the entire array for (i in 0 until n / 2) { val temp = arr[i] arr[i] = arr[n - i - 1] arr[n - i - 1] = temp } // Print the rotated array for (i in arr) { print("$i ") } println()}fun main() { val arr = intArrayOf(1, 3, 5, 7, 9) val n = arr.size val k = 2 // Function Call leftRotate(arr, k, n)}fun leftRotate(arr: IntArray, k: Int, n: Int) { // If k > n, k % n will bring k back in range val rotation = k % n // Reverse the first part of the array (0 to rotation-1) for (i in 0 until rotation / 2) { val temp = arr[i] arr[i] = arr[rotation - i - 1] arr[rotation - i - 1] = temp } // Reverse the second part of the array (rotation to n-1) for (i in 0 until (n - rotation) / 2) { val temp = arr[rotation + i] arr[rotation + i] = arr[n - i - 1] arr[n - i - 1] = temp } // Reverse the entire array for (i in 0 until n / 2) { val temp = arr[i] arr[i] = arr[n - i - 1] arr[n - i - 1] = temp } // Print the rotated array for (i in arr) { print("$i ") } println()}fun main() { val arr = intArrayOf(1, 3, 5, 7, 9) val n = arr.size val k = 2 // Function Call leftRotate(arr, k, n)} |
Output
5 7 9 1 3
Note: the array itself gets updated after the rotation.
Time Complexity: O(n)
Auxiliary Space: O(1), since no extra space has been taken.
This article is contributed by Sridhar Babu and improved by Geetansh Sahni. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
