Multiple left rotations of an array (Efficient)

Software Development
#1

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 temp[0…2n-1] array.
Step 2: Starting position of 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.

  • 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;

}

Output:

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

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

Space optimized Approach: The above method takes extra space. Below given is a space-optimized solution.

// 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;

}

Output:

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