I think the answer is option D. 12.
First of all, please note that this is the second part of a two part question. Part one is here : https://gateoverflow.in/3534/gate2007-it-82
So in part two, we can start anywhere we want.
In this question, we have no. of cylinders N = 2048. My suggestion is that we should look at smaller values of N and see a pattern. (Here, I'm using 1-indexing)
- For N = 2, cardinality of request set is 2. Sequence : 1, 2.
- For N = 4, cardinality of request set is 3. Sequence : 2, 3, 1.
- For N = 8, cardinality of request set is 4. Sequence : 3, 4, 1, 8.
The pattern here is, the cardinality of request set is log(N) + 1. So, log(2048) + 1 = 11 + 1 = 12.
Explanation : Let's try to trace the longest path that we can trace for a given N. This task is easier if we work our way backwards.
- Let's start at cylinder N. Let's assume that N is a power of 2, so N = $2^{n}$
- To maximize the path, we go to cylinder 1. (Sweep = $2^{n}$ - 1)
- From 1, we can go only as far as cylinder $2^{n - 1}$. Because the next cylinder will be closer to the N than 1. (Sweep = $2^{n - 1}$ - 1)
- The next sweep will be of length $2^{n - 2}$ - 1 so that the destination cylinder is closer to our source than 1.
We can see that the problem is now reduced to finding how many numbers of type $2^{i}$ - 1 are there between 1 and N. You can easily verify that the answer will be log(N). That gives us the number of jumps we made. Add 1 to it to get the number of cylinders visited to get the correct answer.