Arrays: Given an array, rotate it one time

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

 

 

 

 

 

 

Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *