Rotate Array ll

Moderate
0/80
profile
Contributed by
9 upvotes
Asked in companies
FloBizTCS

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].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
2 4 7
f
1
3
3 2 1
b
2
Sample output 1 :
7 2 4
1 3 2
Explanation For Sample Output 1:
For the first test case,
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].

For the second test case,
N = 3, num = [3, 2, 1], D = ‘b’, R = 2.
You have to rotate the array 2 times in the backward direction. 
After 1st rotation, the array will be [2, 1, 3].
After 2nd rotation, the array will be [1, 3, 2].
Hence, the output will be [1, 3, 2].
Sample Input 2 :
2
3
4 6 2
f
5
2
9 10
f
0
Sample output 2 :
6 2 4
9 10
Hint

Do a single unit rotation R times.

Approaches (2)
Brute Force

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:

  1. R = R % N.
  2. If D is 'b’.
    • R = N - R.
  3. 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.
Time Complexity

O( N * min(N, R) ), where ‘N’ is the size of the array and 'R' is the number of rotations mod N.

 

We will rotate array ‘R’ times and ‘R’ lies in the range [0, N-1] after the update and for each rotation, it takes O(N) time. So time complexity will be O( N * min(N, R ).

Space Complexity

O( 1 )

 

We are not using any extra space.

Code Solution
(100% EXP penalty)
Rotate Array ll
Full screen
Console