Question

DJ Varun works in a club and plays cool songs. He has N disks of different albums (each of equal radius). Every disk has a distinct number out of 1 to N associated with it. Disks are placed one over the other in a single pile. Varun wants to sort this pile of disks in an increasing order i.e. top to bottom. But he has a very special method of doing this. In a single step he can only choose one disk out of the pile and he can only put it at the top. So the task here is that Varun wants to sort his pile of disks in minimum number of possible steps. What is the minimum number of possible steps to sort the pile so that that Varun can check whether he is doing his work right or wrong?

Input Format

First line contains integer N, the size of the array followed by, an array of size N containing integers 1 to N in any random order which shows the position of disks top to bottom.

Constraints

0 <= N <= 1000

Output Format

Print the Minimum number of steps needed to sort the pile. If it can't be sorted then return output as -1.

ADD COMMENT • link

Entering edit mode

Overview:

Given a sequence of distinct numbers, with the option to move a number from its position to front, what is the minimum number of such moves to make the array sorted?

Observation:

Moving the maximum element to the top is bad, as then every other would again have to move to the top, so that the maximum element ends up at the bottom.
The final move number of each element 1,2,...n, will be in decreasing order.
- Element 1 will be the last moved one.
- Element 2 last move will be before the last move of 1 and after the last move of 3.

Approach:

if the maximum number n is at the position at i, then all number after that needs to be taken to the top at some point.
Similarly, for the second maximum element n-1:
- if it is above n in a pile, then all elements between n-1 and n has to be taken to the top at some time.
- In the case of it below after n, it would have been taken top, so moving it again is not optimal. so all elements between new position of n-1 and n have to be moved.
All other elements are similar, like n-1.
Basically, we don't move n.
- If n-1 is above n, then we don't move n-1 also.
- If n-2 is above n-1 and n-1 is not moved then n-2 will also not move
- If n-3 is above n-2 and n-2 is not moved then n-3 will also not move
- and so on
- this break when a number x is moved
the answer is x

Complexity:

O(N), where N is the number of elements.

Pseudocode:

int Top( vector&lt;int&gt; &amp;V ){
     int find = V.size();
     for( int i = 0; i &lt; V.size(); i++){
          if(a[i] == tofind){
              find--;
          }
     }
     return find;
}

ADD COMMENT • link 2.1 years ago Lokesh 310