SortMachine | Topcoder Archive

Problem Statement

We have a sorting machine that works on a list of distinct numbers. This machine only has one instruction named MOVE that takes one element of the list as a parameter. The MOVE instruction removes the element from the list and then appends it to the end of the remaining list.

For example, the sequence {19,7,8,25} can be sorted in ascending order using 2 instructions:
MOVE 19, to get {7,8,25,19}
MOVE 25, to get {7,8,19,25}

You will be given a int[] a containing a list of distinct numbers. Return the minimum number of instructions required to sort the list in ascending order.

Definition

Class:: SortMachine
Method:: countMoves
Parameters:: int[]
Returns:: int
Method signature:: int countMoves(int[] a)
(be sure your method is public)

Constraints

a will have between 1 and 50 elements, inclusive.
Each element of a will be between -1000 and 1000, inclusive.
All elements of a will be distinct.

Examples

```
{19,7,8,25}
```
```
Returns: 2
```
The example from the problem statement.
```
{1,2,3,4,5}
```
```
Returns: 0
```
This list is already sorted, so no instructions are needed.
```
{1000,-1000,0}
```
```
Returns: 1
```
This list can be sorted with a single instruction: MOVE 1000.
```
{1,3,4,5,6,7,8,9,2}
```
```
Returns: 7
```
```
{-2, -8, 9, 0}
```
```
Returns: 3
```

{976, -946, -824, 680, -644, -95, 128, -892, 816, -263,
 -592, -669, 887, 447, -653, -759, 572, 171, 635, 98,
 -904, 78, 143, -416, -40, -846, 784, -702, -738, -858,
 582, 603, -535, 529, 84, -964, 934, 36, 783}

Returns: 38

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.