Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R].
How to find out the position of a number after these operations are applied?
For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2.
Reverse elements between 1, and 3, the array becomes [3, 2, 1, 4, 5]
Reverse elements between 3, and 5, the array becomes [3, 2, 5, 4, 1]
Reverse elements between 2, and 5, the array becomes [3, 1, 4, 5, 2]
So the final position of 2 is 5.
This problem was originally appeared in Codechef.
If we want to track just one number, we need not perform reversal operations everytime. This process takes O(n^2) time in worst case.
As we perform the reversal operations, we just need to track what is the new position of target number.
How do we track the position?
Consider the positions L = left, R= right, C = current and the distance between L and C is X,
After we reverse the elements between L, R, C will be placed x steps before R
C – L = R – X
X = R + L – C
The new position of C will be (R+L-C)
The position of C will not be altered if we are reversing the part which includes C.
Here is the C++ code for the same which runs in O(n) time.