Circular Array Rotation : HackerRank Solution in Python.
John Watson knows of an operation called a right circular rotation on an array of integers. One rotation operation moves the last array element to the first position and shifts all remaining elements right one. To test Sherlock’s abilities, Watson provides Sherlock with an array of integers. Sherlock is to perform the rotation operation a number of times then determine the value of the element at a given position.
For each array, perform a number of right circular rotations and return the value of the element at a given index.
For example, array a=[3,4,5], number of rotations k=2, and indices to check, m= [1,2].
First we perform the two rotations:
[3,4,5]->[5,3,4]->[4,5,3]
Now return the values from the zero-based indices and as indicated in the array.
a[1]=5
a[2]=3
Solution in Python.
First, we will declare the length of array a in a variable n in the given function.
Instead of circularly rotating the array manually, if we reduce the magnitude of given number of rotations i.e k from the length of array i.e n we will get a number which will be the first index of the array a after the k right circular rotations rotations, that is, the expression
n-k
Now, we will add the queries or the indices to check in the array after performing the k right circular rotations. Therefore the expression will be
n-k+q
Albeit, if the value of expression (n-k+q) exceeds n-1 the array will get out of bounds. In order to commence the index from the start will have to add a modulus of n after the expression. Thus the expression, for the qth index of array a after k right circular rotation is
(n-k+q)%n
In, above code we declare an empty list and iterate through the array containing queries and append the values of expression
a[(n-k+q)%n]
in the afore declared array ans. Finally we will return the ans list.
Note : If instead of following the above approach, we manually rotate the array, the script will exceed runtime limit set by HackerRank and the script won’t pass all the test cases.
