FastPrep

Description

Solutions

Exchange Cups

📚RELATED PROBLEMS

tomtom's note: Not entirely sure if this question is from TikTok, but I included it in the collection just in case :))

The store has a lot of cups, numbered 1~N on the shelf. For example, there are 5 cups:

2 1 3 5 4

Ask to pick up 2 cups at a time and swap their positions. After several times, the serial number of the cups is made:

1 2 3 4 5

For such a simple case, obviously, at least 2 swaps are required to reset.

The input format is two lines:

Line 1:

A positive integer N (N < 10000) representing the number of bottles

Second line:

N positive integers, separated by spaces, indicating the current arrangement of the bottles.

The output data is a positive integer in a row, indicating at least how many times to swap to complete the sorting.

Function Description

Complete the function exchangeCups in the editor below.

exchangeCups has the following parameter(s):

int labels[N]: an array of integers

Constraints

N (N < 10000)

Example 1:

Input:  labels = [3, 1, 2, 5, 4]
Output: 3 
Explanation:
      
        To sort the array [3, 1, 2, 5, 4] with the minimum number of swaps:
      
      
        Swap the cups at positions 1 and 2 to get [1, 3, 2, 5, 4].
        Swap the cups at positions 2 and 3 to get [1, 2, 3, 5, 4].
        Finally, swap the cups at positions 4 and 5 to get [1, 2, 3, 4, 5].
      
      
        Therefore, a minimum of 3 swaps are required to sort the cups.

Constraints:

N < 10000