Difficulty : CakeWalk
Pre-requisites : basic language data structures
At first, let’s note that if we rotate the array by K units anticlockwise, it’s the same as the rotation by N-K units clockwise. So, from now on, we will consider only clockwise rotations. In case we have any anticlockwise rotation query, it can be reduced to the clockwise one.
When we rotate the array by K units anticlockwise, its’ first element becomes equal to the K mod N+1-th element of the initial array. The second element of this rotated array will be equal to (K+1) mod N+1-th element of the initial array, the third will be equal to the (K+2) mod N+1-th one, and so on (of course, we use 1-indexation in our considerations). So, using this facts one can simply get the M-th element of the array after a rotation.
What happens when we have several rotations? One can note that the rotations are “additive”, so we only need to maintain is the current “shift” variable that points to the first element of the current array after all the rotations. If this “shift” variable equals to R before some clockwise turn, it will be equal to (R+K) mod N after this turn. Basically, like it is described in the previous paragraph, we can get the M-th element of the current array as A[(R+M-1) mod N], where A is the array that was given initially.
In this solution we don’t actually rotate the array, we only operate with out “shift” variable (R above). So each operation is performed in O(1) time, so we get the total complexity of O(N+Q) where N is the size of the array and Q is the number of queries.
Setter’s solution: link
Tester’s solution: link