Last Updated: 5 Apr, 2022

Rotate Array ll

Moderate

Asked in companies

Solve now

Problem statement

You are given an array ‘NUM’ containing ‘N’ integers, the direction of rotation ‘D’, and the number of rotations ‘R’.

You have to rotate the given array ‘R’ times. If the direction of rotation ‘D’ has a value equal to ‘f’ then you have to rotate the array forward else if it has a value equal to ‘b’ then rotate the array backward.

For Example :

If N = 3, num = [2, 4, 7], D = ‘f’, R = 1.
You have to rotate the array 1 time in the forward direction. Hence, the output will be [7, 2, 4].

Input Format :

The first line of the input contains an integer, 'T’, denoting the number of test cases.

The first line of each test case will contain a single integer ‘N’, denoting the size of the array.

The second line of each test case contains ‘N’ space-separated integers denoting elements of the array.

The third line of each test case will contain a single lowercase English character “f" or “b”, denoting the direction of rotation.

The fourth line of each test case will contain a single integer ‘R’, denoting the number of rotations.

Output Format :

For each test case, print the array after rotation.

Print a separate line for each test case.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 100000
1 <= num[i] <= 10^7
D = {‘f’, ‘b’}
0 <= R <= 10^7
Sum of N over all the test cases will not exceed 10^5

Time limit: 1 sec

Solve now

Approaches

01 Approach

The first thing to notice here is that if we rotate an array of size ‘N’ ‘R’ times it is equivalent to rotating it (R % N) times as after ‘N’ rotations the array will regain its original state, so we assume ‘R’ to be lie in the range [0, N-1]. The second thing to notice is that if we rotate the array forward ‘R’ times then the ’R’ elements from the back will come in front for example N=3, array = [1, 2, 3] R = 2 after 2 operations array will become [2, 3, 1] Similarly we can say that if we rotate array ‘R’ times in backward direction then the ‘R’ elements from the front will go to back So, it is equivalent to rotate array ‘R’ times forward and N - R times backward so, we will focus only on rotating the array forward.

To rotate an array forward 1 time we have to just shift every element of the array by 1 in the forward direction and for the last element, we will put it in 1st position So, repeat this process ‘R’ times to get the desired rotated array.

Here is the algorithm:

R = R % N.
If D is 'b’.
- R = N - R.
Doing shifting operation ‘R’ times (say iterator ‘i’)
- curr = num[N - 1].
- Iterate over the array (say iterator ‘i’)
  - temp = num[i].
  - num[i] = curr.
  - curr = temp.

Solve now

02 Approach

The basic idea is to observe that if we rotate the array forward ‘R’ times then the ’R’ elements from the back will come in front, for example, if N = 3, array = [1, 2, 3], R = 2 after 2 operations array will become [2, 3, 1], here we can see that [2, 3] comes forward. Let’s divide the array into parts p1 and p2 where p2 is the part that represents the last ‘R’ elements of the array and p1 is the part representing the remaining N - R elements initially the array is p1 p2 we have to make the array p2 p1, we can do it by reversing p1 and p2 separately and then reverse the array whole.

Initially, the array is p1 p2 after reversing p1, p2 it becomes p1’ p2’ after reversing the array whole it becomes p2 p1 hence we rotate the array forward ‘R’ times.

Here is the algorithm :

reverse_segment function:
- While ‘l’ is less than ‘r’
  - swap( arr[l], arr[r] ).
  - l += 1, r -= 1.
given function:
- R = R % N.
- If D is 'b'
  - R= N - R.
- reverse_segment( 0, N-R-1, num ).
- reverse_segment( N-R, N-1, num ).
- reverse_segment( 0, N-1, num ).

Solve now