PROBLEM LINK:
PROBLEM NAME: Quarrels of Tom and Jerry
Author: Learners Club
DIFFICULTY:
MEDIUM
PREREQUISITES:
ADHOC
PROBLEM:
In short, Assume an array upto N and we have been given a series of discards , where in we will remove all the numnber from the lower index
of the discards to the upper index (inclusive) and then shift the adjacent elements to take its place. The required answer is the value present
at the Kth index.
EXPLANATION:
The simplest way to solve this problem is to consider the sequence of events in reverse. Think what problems you will end up in if you consider to do the discards in the given sequence ?
First, consider where the kth element of the sequence would have been before the final discards. Then the discards before that, and so on.
We handle each discards the same way, and after we have undone all of the discardss, we end up with the initial position.
So, then all that remains is to figure out exactly how to undo a discards.
Let the index of the number after the discards be k and the discards be given be lo and hi.
If lo is greater than k, then the discards of the elements may not effect the sequence, as each element removed comes later than the kth and does not effect its position. If, on the other hand, lo is less than or equal to k, then each element removed came before k, and so we set k = k + hi - lo + 1.
And we keep on doing the above for all the discards or if K becomes greater than N we stop since we only have N elements and -1 as Answer