Skip to content
Get started

Fewest swaps to sort a permutation

The array [4, 7, 1, 9, 3, 10, 2, 8, 5, 6] holds a permutation of 1..101..10. A move swaps the contents of any two positions (not necessarily adjacent). What is the minimum number of moves needed to sort it into [1, 2, ..., 10]?

Show hints (2)+
  1. Follow position →\to value →\to position ... until you return; that is a cycle.
  2. How many swaps does a cycle of length kk need?

Answer

Reveal answer →

6

Create a free account to see the full worked solution and track your progress.

Interview format: Prop Trading

Related questions