Rotate Array

Difficulty Level Medium
Frequently asked in Amazon Apple MakeMyTrip MAQ Microsoft Oracle SAP SAP Labs Wipro
Array GreedyViews 2618

Rotate array is a problem in which we have given an array of size N. We have to rotate the array in the right direction. Each element shift by one position right and last element of the array come to the first position. So, we have given a value K and we have to shift the array K times towards right and then print the final array. Let’s see how to rotate the array by shifting all elements toward the right by taking an example.

Rotate Array

Input Format

First line containing two integer values N and K denoting the number of elements in the input array and number of right shifts perform on a given array.

The second line containing an input array which have N integer values.

Output Format

The first line containing the final array after performing K right shift.

Constraints

  • 1<=N<=100000
  • -10^9<=A[i]<=10^9
  • 1<=k<=10^9
8 4
1 5 9 6 5 4 2 7
2 7 1 5 9 6 5 4

Explanation

In the given array first, we reverse all the array. After it reverses the array from beginning to (K%N-1). After this, we swap the last remaining elements and got the final array which comes after K right shift.

Rotate Array

Algorithm For Rotate Array

Step:1 Reverse all the array.
Step:2 Reverse first K%N elements.
Step:3 Reverse last N-K%N elements.
Step:4 Print the final array.

Implementation For Rotate Array

/*C++ Implementation of Rotate Array.*/ 
#include<bits/stdc++.h> 
using namespace std; 
int main() 
{ 
    /*input values.*/ 
    int n,k; 
    cin>>n>>k;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        a.push_back(x);
    }
    reverse(a.begin(),a.end());
    reverse(a.begin(),a.begin()+k%n);
    reverse(a.begin()+k%n,a.end());
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    return 0; 
}
13 17
1 6 24 65 13 -234 0 12 54 3 -1 6 3
3 -1 6 3 1 6 24 65 13 -234 0 12 54

Time Complexity

O(N) where N is the size of the input array. Here we use the reverse function which takes linear time to reverse the number. Here maximum we reverse all the input array. So, our maximum time complexity will be O(N).

Space Complexity

O(1) because we don’t use any extra space here. We use the reverse function which takes O(1) space to reverse the number.

References

Translate ยป