Finding the number in a shuffled array | Letuscode
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 After we reverse the elements between L, R,Read full article from Finding the number in a shuffled array | Letuscode
No comments:
Post a Comment