need ur approach here

The head of a hard disk serves requests following the shortest seek time first (SSTF) policy.

What is the maximum cardinality of the request set, so that the head changes its direction after servicing every request if the total number of tracks are $2048$ and the head can start from any track?

- $9$
- $10$
- $11$
- $12$

### 16 Comments

Hi Guys,

This is good question. Think on following points -

- Why can we not have multiple seek series ?
- Why is greedy algo. working ?
- Why are we starting from 1 ?
- Does starting points matters ?

PS: Think in terms of seek sequence. For answer hint check @Debashish Deka ji's top comment.

thank you @ Chhotu for comment

Hi Guys,

This is good question. Think on following points -

- Why can we not have multiple seek series ?
- Why is greedy algo. working ?
- Why are we starting from 1 ?
- Does starting points matters ?

I tried by self and got the some logic. which was correct.

really beautiful question. :)

A slightly different explanation:

Let's say our track head is at position 0 and our track numbers go in both directions around 0. To ensure that we always change directions and that we do this as many times as possible, we have to go right **1 track **to get +1, then left **3 tracks **to get -2, then right again **7** **tracks **to get +5,and so on...

$0 \rightarrow +1 \rightarrow -2 \rightarrow +5 \rightarrow ...$

Notice that in each step, we move exactly $2^n - 1$ tracks to the left and right in alternating fashion, where $n$ is the step number. For example, we moved $1 (=2^1 - 1)$ track to the right in the first step, $3 (= 2^2 - 1)$ tracks in the second step and so on.

The critical thing to remember is this:

Our limit of at most 2048 tracks will be reached exactly when

the next step requires us to move more than 2047 places.

Or in other words, as soon as we need to move more than 2047 tracks in the next step, we know that we can't, and then stop.

So in our last step, we can choose to move $2047 (= 2^{11} - 1)$ places. So total number of steps = 11. These steps represent the track numbers other than the track 0 that we started with. So there are 11 + 1 = 12 elements (track numbers) in the request set.

So the correct answer is** D. 12 **

EDIT: Since the question mentions that “the head changes its direction after servicing every request”, the track on which the head is at the start cannot be considered a request (since the direction doesn’t change after servicing it). So, the correct answer is **C. 11**

Re-posting image of @Skscool007 in correct viewing angle. Note that in above comment, i started with track no. 683 and initially movement done in right side, but @Skscool007 started with track no. 1366 (i.e 2048-682) and initially movement done in Left side.

Due to this reason, we able to get** two "request set" with maximum possible cardinality.**

Initially head will be at some position or moving in some specific direction then we should not take current position of head in cardinality of the request because if we do so then head will not change it's direction if request come at track on which it is currently there.

So that's why you are getting 12.

Because of above reason you should remove one track (initial position of head) and answer should be 11.

I hope it will help others who are confused in the battle of 11 and 12.

## 13 Answers

**answer should be 12.**

consider this sequence: 1,513,641,673,681,683,684,688,704,768,1024,2048.

And head starts at 683.

**How I got this sequence?**

Above answers explains that max distance should be 2047.

Then we derive this sequence in out-to-in order.

2048 is reached from 1 (dist = 2047)

1 is reached from 1024 (dist = 1023)

1024 is reached from 513 (dist = 511)

......

As we already know from the previous answers that the difference between the sequence of requests will be like 1,3,7,15,31,63,127,511,1023,2047 and head can start from any position then we can start the zigzag line from backward i.e from 2048 to 1 (or we can do from 1 to 2048)

We can do it till the difference is 1.

So answer will be 11.

*As it is asked about the about cardinality of requeste set i.e the number of requests (not how many times it changed its direction) then it will be 11, as requests are 684, 681, 688, 673, 704, 641, 768, 513, 1024, 1, 2048.

*Here the head (683) is not included because head it self is not a request of the current request set.