What is Quickly find multiple left rotations of an array | Set 1?

In this article, we will learn Quickly find multiple left rotations of an array | Set 1,This free Data Structures and Algorithms tutorial for complete beginners will help you learn Data Structures and Algorithms from scratch.

Quickly find multiple left rotations of an array

Given an array of size n and multiple values around which we need to left rotate the array. How to quickly find 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

Simple Approach: We have already discussed different approaches given in the below posts.

The best of the above approaches take O(n) time and O(1) extra space.

Simple Approach: We are using the reverse algorithm but this time for multiple k values – you can click on the above link to understand this approach.

Implementation:

C++

// C++ program for the above approach 
#include <iostream> 
using namespace std; 
int* rotateArray(int A[], int start, int end) 
{ 
    while (start < end) { 
        int temp = A[start]; 
        A[start] = A[end]; 
        A[end] = temp; 
        start++; 
        end--; 
    } 
    return A; 
} 
void leftRotate(int A[], int a, int k) 
{ 
    // if the value of k ever exceeds the length of the 
    // array 
    int c = k % a; 
  
    // initializing array D so that we always 
    // have a clone of the original array to rotate 
    int D[a]; 
    for (int i = 0; i < a; i++) 
        D[i] = A[i]; 
  
    rotateArray(D, 0, c - 1); 
    rotateArray(D, c, a - 1); 
    rotateArray(D, 0, a - 1); 
  
    // printing the rotated array 
    for (int i = 0; i < a; i++) 
        cout << D[i] << " "; 
    cout << "\n"; 
} 
int main() 
{ 
    int A[] = { 1, 3, 5, 7, 9 }; 
    int n = sizeof(A) / sizeof(A[0]); 
  
    int k = 2; 
    leftRotate(A, n, k); 
  
    k = 3; 
    leftRotate(A, n, k); 
  
    k = 4; 
    leftRotate(A, n, k); 
    return 0; 
} 
// this code is contributed by aditya942003patil

Java

/*package whatever //do not write package name here */
  
import java.io.*; 
import java.util.Arrays; 
class GFG { 
    public static void leftRotate(int[] A, int a, int k) 
    { 
        // if the value of k ever exceeds the length of the 
        // array 
        int c = k % a; 
  
        // initializing array D so that we always 
        // have a clone of the original array to rotate 
        int[] D = A.clone(); 
  
        rotateArray(D, 0, c - 1); 
        rotateArray(D, c, a - 1); 
        rotateArray(D, 0, a - 1); 
  
        // printing the rotated array 
        System.out.print(Arrays.toString(D)); 
        System.out.println(); 
    } 
  
    // Function to rotate the array from start index to end 
    // index 
    public static int[] rotateArray(int[] A, int start, 
                                    int end) 
    { 
        while (start < end) { 
            int temp = A[start]; 
            A[start] = A[end]; 
            A[end] = temp; 
            start++; 
            end--; 
        } 
        return A; 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        int A[] = { 1, 3, 5, 7, 9 }; 
        int n = A.length; 
  
        int k = 2; 
        leftRotate(A, n, k); 
  
        k = 3; 
        leftRotate(A, n, k); 
  
        k = 4; 
        leftRotate(A, n, k); 
    } 
}

Python3

# Python3 implementation of left rotation 
# of an array K number of times 
  
# Fills temp with two copies of arr 
  
  
def rotateArray(A, start, end): 
  
    while start < end: 
        temp = A[start] 
        A[start] = A[end] 
        A[end] = temp 
        start += 1
        end -= 1
    return A 
  
# Function to left rotate an array k times 
  
  
def leftRotate(arr, a, k): 
  
    # if the value of k ever exceeds the length of the array 
    c = k % a 
  
    # initializing array D so that we always 
    # have a clone of the original array to rotate 
    D = arr.copy() 
  
    rotateArray(D, 0, c - 1) 
    rotateArray(D, c, a - 1) 
    rotateArray(D, 0, a - 1) 
  
    # printing the rotated array 
    print(D) 
  
  
# Driver program 
arr = [1, 3, 5, 7, 9] 
n = len(arr) 
  
k = 2
leftRotate(arr, n, k) 
  
k = 3
leftRotate(arr, n, k) 
  
k = 4
leftRotate(arr, n, k) 
  
# This code is contributed by aditya942003patil 

C#

// C# program for the above approach 
  
using System; 
  
public class GFG { 
  
    public static void leftRotate(int[] A, int a, int k) 
    { 
        // if the value of k ever exceeds the length of the 
        // array 
        int c = k % a; 
  
        // initializing array D so that we always 
        // have a clone of the original array to rotate 
        int[] D = A.Clone() as int[]; 
  
        rotateArray(D, 0, c - 1); 
        rotateArray(D, c, a - 1); 
        rotateArray(D, 0, a - 1); 
  
        // printing the rotates array 
        Console.Write("["); 
        for (int i = 0; i < D.Length - 1; i++) { 
            Console.Write(D[i] + " "); 
        } 
        Console.WriteLine(D[D.Length - 1] + "]"); 
    } 
  
    // Function to rotate the array from start index to end 
    // index 
    public static int[] rotateArray(int[] A, int start, 
                                    int end) 
    { 
        while (start < end) { 
            int temp = A[start]; 
            A[start] = A[end]; 
            A[end] = temp; 
            start++; 
            end--; 
        } 
        return A; 
    } 
  
    static public void Main() 
    { 
  
        // Code 
        int[] A = { 1, 3, 5, 7, 9 }; 
        int n = A.Length; 
  
        int k = 2; 
        leftRotate(A, n, k); 
  
        k = 3; 
        leftRotate(A, n, k); 
  
        k = 4; 
        leftRotate(A, n, k); 
    } 
} 
  
// This code is contributed by lokeshmvs21.

Javascript

class GFG 
{ 
    static leftRotate(A, a, k) 
    { 
        // if the value of k ever exceeds the length of the array 
        var c = k % a; 
          
        // initializing array D so that we always 
        // have a clone of the original array to rotate 
        var D = [...A]; 
        GFG.rotateArray(D, 0, c - 1); 
        GFG.rotateArray(D, c, a - 1); 
        GFG.rotateArray(D, 0, a - 1); 
          
        // printing the rotated array 
        console.log(D); 
        console.log(); 
    } 
      
    // Function to rotate the array from start index to end index 
    static rotateArray(A, start, end) 
    { 
        while (start < end) 
        { 
            var temp = A[start]; 
            A[start] = A[end]; 
            A[end] = temp; 
            start++; 
            end--; 
        } 
        return A; 
    } 
      
    // Driver Code 
    static main(args) 
    { 
        var A = [1, 3, 5, 7, 9]; 
        var n = A.length; 
        var k = 2; 
        GFG.leftRotate(A, n, k); 
        k = 3; 
        GFG.leftRotate(A, n, k); 
        k = 4; 
        GFG.leftRotate(A, n, k); 
    } 
} 
GFG.main([]);

Output

5 7 9 1 3 
7 9 1 3 5 
9 1 3 5 7

Time Complexity: O(n)
Auxiliary Space: O(n)

Efficient Approach:

The above approaches work well when there is a single rotation required. The approaches also modify the original array. To handle multiple queries of array rotation, we use a temp array of size 2n and quickly handle rotations.

Step 1: Copy the entire array two times in the temp[0..2n-1] array.
Step 2: Starting position of the array after k rotations in temp[] will be k % n. We do k
Step 3: Print temp[] array from k % n to k % n + n.

Implementation:

C++

// CPP implementation of left rotation of 
// an array K number of times 
#include <bits/stdc++.h> 
using namespace std; 
  
// Fills temp[] with two copies of arr[] 
void preprocess(int arr[], int n, int temp[]) 
{ 
    // Store arr[] elements at i and i + n 
    for (int i = 0; i < n; i++) 
        temp[i] = temp[i + n] = arr[i]; 
} 
  
// Function to left rotate an array k times 
void leftRotate(int arr[], int n, int k, int temp[]) 
{ 
    // Starting position of array after k 
    // rotations in temp[] will be k % n 
    int start = k % n; 
  
    // Print array after k rotations 
    for (int i = start; i < start + n; i++) 
        cout << temp[i] << " "; 
  
    cout << endl; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = { 1, 3, 5, 7, 9 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    int temp[2 * n]; 
    preprocess(arr, n, temp); 
  
    int k = 2; 
    leftRotate(arr, n, k, temp); 
  
    k = 3; 
    leftRotate(arr, n, k, temp); 
  
    k = 4; 
    leftRotate(arr, n, k, temp); 
  
    return 0; 
}

Java

// Java implementation of left rotation of 
// an array K number of times 
class LeftRotate { 
    // Fills temp[] with two copies of arr[] 
    static void preprocess(int arr[], int n, int temp[]) 
    { 
        // Store arr[] elements at i and i + n 
        for (int i = 0; i < n; i++) 
            temp[i] = temp[i + n] = arr[i]; 
    } 
  
    // Function to left rotate an array k time 
    static void leftRotate(int arr[], int n, int k, 
                           int temp[]) 
    { 
        // Starting position of array after k 
        // rotations in temp[] will be k % n 
        int start = k % n; 
  
        // Print array after k rotations 
        for (int i = start; i < start + n; i++) 
            System.out.print(temp[i] + " "); 
  
        System.out.print("\n"); 
    } 
  
    // Driver program 
    public static void main(String[] args) 
    { 
        int arr[] = { 1, 3, 5, 7, 9 }; 
        int n = arr.length; 
  
        int temp[] = new int[2 * n]; 
        preprocess(arr, n, temp); 
  
        int k = 2; 
        leftRotate(arr, n, k, temp); 
  
        k = 3; 
        leftRotate(arr, n, k, temp); 
  
        k = 4; 
        leftRotate(arr, n, k, temp); 
    } 
} 
/*This code is contributed by Prakriti Gupta*/

Python3

# Python3 implementation of left rotation 
# of an array K number of times 
  
# Fills temp with two copies of arr 
  
  
def preprocess(arr, n): 
    temp = [None] * (2 * n) 
  
    # Store arr elements at i and i + n 
    for i in range(n): 
        temp[i] = temp[i + n] = arr[i] 
    return temp 
  
# Function to left rotate an array k times 
  
  
def leftRotate(arr, n, k, temp): 
  
    # Starting position of array after k 
    # rotations in temp will be k % n 
    start = k % n 
  
    # Print array after k rotations 
    for i in range(start, start + n): 
        print(temp[i], end=" ") 
    print("") 
  
  
# Driver program 
arr = [1, 3, 5, 7, 9] 
n = len(arr) 
temp = preprocess(arr, n) 
  
k = 2
leftRotate(arr, n, k, temp) 
  
k = 3
leftRotate(arr, n, k, temp) 
  
k = 4
leftRotate(arr, n, k, temp) 
  
# This code is contributed by Sanghamitra Mishra 

C#

// C# implementation of left rotation of 
// an array K number of times 
using System; 
class LeftRotate { 
    // Fills temp[] with two copies of arr[] 
    static void preprocess(int[] arr, int n, int[] temp) 
    { 
        // Store arr[] elements at i and i + n 
        for (int i = 0; i < n; i++) 
            temp[i] = temp[i + n] = arr[i]; 
    } 
  
    // Function to left rotate an array k time 
    static void leftRotate(int[] arr, int n, int k, 
                           int[] temp) 
    { 
        // Starting position of array after k 
        // rotations in temp[] will be k % n 
        int start = k % n; 
  
        // Print array after k rotations 
        for (int i = start; i < start + n; i++) 
            Console.Write(temp[i] + " "); 
        Console.WriteLine(); 
    } 
  
    // Driver program 
    public static void Main() 
    { 
        int[] arr = { 1, 3, 5, 7, 9 }; 
        int n = arr.Length; 
  
        int[] temp = new int[2 * n]; 
        preprocess(arr, n, temp); 
  
        int k = 2; 
        leftRotate(arr, n, k, temp); 
  
        k = 3; 
        leftRotate(arr, n, k, temp); 
  
        k = 4; 
        leftRotate(arr, n, k, temp); 
    } 
} 
// This code is contributed by vt_m.

PHP

<?php  
// PHP implementation of  
// left rotation of an  
// array K number of times 
  
// Fills $temp with 
// two copies of $arr 
function preprocess(&$arr, $n,  
                    &$temp) 
{ 
    // Store $arr elements 
    // at i and i + n 
    for ($i = 0; $i < $n; $i++) 
        $temp[$i] = $temp[$i + $n] = $arr[$i]; 
} 
  
// Function to left rotate 
// an array k times 
function leftRotate(&$arr, $n, 
                     $k, &$temp) 
{ 
    // Starting position of  
    // array after k rotations 
    // in temp[] will be k % n 
    $start = $k % $n; 
  
    // Print array after 
    // k rotations 
    for ($i = $start;  
         $i < $start + $n; $i++) 
        echo $temp[$i] . " "; 
  
    echo "\n"; 
} 
  
// Driver Code 
$arr = array(1, 3, 5, 7, 9); 
$n = sizeof($arr); 
  
$temp[2 * $n] = array(); 
preprocess($arr, $n, $temp); 
  
$k = 2; 
leftRotate($arr, $n, $k, $temp); 
  
$k = 3; 
leftRotate($arr, $n, $k, $temp); 
  
$k = 4; 
leftRotate($arr, $n, $k, $temp); 
  
// This code is contributed 
// by ChitraNayal 
?>

Javascript

<script> 
  
// Javascript implementation of left rotation of 
// an array K number of times 
  
    // Fills temp with two copies of arr 
    function preprocess(arr , n , temp) { 
        // Store arr elements at i and i + n 
        for (i = 0; i < n; i++) 
            temp[i] = temp[i + n] = arr[i]; 
    } 
  
    // Function to left rotate an array k time 
    function leftRotate(arr , n , k , temp) { 
        // Starting position of array after k 
        // rotations in temp will be k % n 
        var start = k % n; 
  
        // Print array after k rotations 
        for (i = start; i < start + n; i++) 
            document.write(temp[i] + " "); 
  
        document.write("<br/>"); 
    } 
  
    // Driver program 
      
        var arr = [ 1, 3, 5, 7, 9 ]; 
        var n = arr.length; 
  
        var temp = Array(2 * n).fill(0); 
        preprocess(arr, n, temp); 
  
        var k = 2; 
        leftRotate(arr, n, k, temp); 
  
        k = 3; 
        leftRotate(arr, n, k, temp); 
  
        k = 4; 
        leftRotate(arr, n, k, temp); 
  
// This code contributed by gauravrajput1  
  
</script>

Output

5 7 9 1 3 
7 9 1 3 5 
9 1 3 5 7

Time Complexity: O(n)
Note that the task to find starting address of rotation takes O(1) time. It is printing the elements that take O(n) time.

Auxiliary Space: O(n)

Space-optimized Approach: The above method takes extra space. Below given is a space-optimized solution. Thanks to frenzy77 for suggesting this approach.

Implementation:

C++

// CPP implementation of left rotation of 
// an array K number of times 
#include <bits/stdc++.h> 
using namespace std; 
  
// Function to left rotate an array k times 
void leftRotate(int arr[], int n, int k) 
{ 
    // Print array after k rotations 
    for (int i = k; i < k + n; i++) 
        cout << arr[i % n] << " "; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = { 1, 3, 5, 7, 9 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    int k = 2; 
    leftRotate(arr, n, k); 
    cout << endl; 
  
    k = 3; 
    leftRotate(arr, n, k); 
    cout << endl; 
  
    k = 4; 
    leftRotate(arr, n, k); 
    cout << endl; 
  
    return 0; 
}

Java

// Java implementation of 
// left rotation of an 
// array K number of times 
  
import java.io.*; 
  
class GFG { 
  
    // Function to left rotate 
    // an array k times 
    static void leftRotate(int arr[], int n, int k) 
    { 
        // Print array after 
        // k rotations 
        for (int i = k; i < k + n; i++) 
            System.out.print(arr[i % n] + " "); 
    } 
  
    // Driver Code 
    public static void main(String[] args) 
    { 
        int arr[] = { 1, 3, 5, 7, 9 }; 
        int n = arr.length; 
  
        int k = 2; 
        leftRotate(arr, n, k); 
        System.out.println(); 
  
        k = 3; 
        leftRotate(arr, n, k); 
        System.out.println(); 
  
        k = 4; 
        leftRotate(arr, n, k); 
        System.out.println(); 
    } 
} 
  
// This code is contributed by ajit

Python 3

# Python3 implementation of 
# left rotation of an array 
# K number of times 
  
# Function to left rotate 
# an array k times 
  
  
def leftRotate(arr, n, k): 
  
    # Print array 
    # after k rotations 
    for i in range(k, k + n): 
        print(str(arr[i % n]), 
              end=" ") 
  
  
# Driver Code 
arr = [1, 3, 5, 7, 9] 
n = len(arr) 
k = 2
leftRotate(arr, n, k) 
print() 
  
k = 3
leftRotate(arr, n, k) 
print() 
  
k = 4
leftRotate(arr, n, k) 
print() 
  
# This code is contributed 
# by ChitraNayal 

C#

// C# implementation of 
// left rotation of an 
// array K number of times 
using System; 
  
class GFG { 
  
    // Function to left rotate 
    // an array k times 
    static void leftRotate(int[] arr, int n, int k) 
    { 
        // Print array after 
        // k rotations 
        for (int i = k; i < k + n; i++) 
            Console.Write(arr[i % n] + " "); 
    } 
  
    // Driver Code 
    static public void Main() 
    { 
        int[] arr = { 1, 3, 5, 7, 9 }; 
        int n = arr.Length; 
  
        int k = 2; 
        leftRotate(arr, n, k); 
        Console.WriteLine(); 
  
        k = 3; 
        leftRotate(arr, n, k); 
        Console.WriteLine(); 
  
        k = 4; 
        leftRotate(arr, n, k); 
        Console.WriteLine(); 
    } 
} 
  
// This code is contributed 
// by akt_mit

PHP

<?php 
  
// PHP implementation of left rotation of 
// an array K number of times 
  
// Function to left rotate an array k times 
function leftRotate($arr, $n, $k) 
{ 
      
    // Print array after k rotations 
    for ($i = $k; $i < $k + $n; $i++) 
        echo $arr[$i % $n] ," "; 
} 
  
// Driver program 
$arr = array (1, 3, 5, 7, 9); 
$n = sizeof($arr); 
  
$k = 2; 
leftRotate($arr, $n, $k); 
echo "\n"; 
  
$k = 3; 
leftRotate($arr, $n, $k); 
echo "\n"; 
  
$k = 4; 
leftRotate($arr, $n, $k); 
echo "\n"; 
  
// This code is contributed by aj_36 
?>

Javascript

<script> 
  
// JavaScript implementation of  
// left rotation of an  
// array K number of times 
  
  
// Function to left rotate 
// an array k times 
function leftRotate(arr, n, k) 
{ 
    // Print array after 
    // k rotations 
    for (let i = k; i < k + n; i++) 
        document.write(arr[i % n] + " "); 
} 
  
// Driver Code 
  
let arr = [1, 3, 5, 7, 9]; 
n = arr.length; 
  
k = 2; 
leftRotate(arr, n, k); 
document.write("<br>"); 
  
k = 3; 
leftRotate(arr, n, k); 
document.write("<br>"); 
  
k = 4; 
leftRotate(arr, n, k); 
document.write("<br>"); 
  
  
  
</script>

Output

5 7 9 1 3 
7 9 1 3 5 
9 1 3 5 7

Time Complexity: O(n)
Auxiliary Space: O(1)