Exchange Cups
TikTok● MediumOAProblem statement
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
exchangeCups(labels: int[]) → int
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)
Examples
Example 1
labels = [3, 1, 2, 5, 4]return = 3To 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