Editorial-QM14A

editorial
,
1

#PROBLEM LINK:

Practice
Contest

Author: Chandan Boruah
Tester: Chandan Boruah
Editorialist: Chandan Boruah

#DIFFICULTY:
EASY

#PREREQUISITES:
Brute Force

#PROBLEM:
Given a numbers from 0 to N-1, find the minimum number of swaps needed to sort numbers in ascending order.

#QUICK EXPLANATION:
If the number is in correct position don’t do anything. Else keep swapping the number till it reaches the correct position, keeping count.

#EXPLANATION:
If the number is in correct position don’t do anything. If not, then the swaps needs to be performed till the number reaches in correct position. For example, [3] 0 1 [2]. Here first swap will cause [2] 0 1 [3], then 3 is in correct position. After that [0] [2] 1 3, then 0 [1] [2] 3. Requiring a total of 3 swaps.

#AUTHOR’S AND TESTER’S SOLUTIONS:

using System;
using System.Collections.Generic;
class some
{
	public static void Main()
	{
		int num=int.Parse(Console.ReadLine());
		string[]ss=Console.ReadLine().Split();
		int[]arr=new int[ss.Length];
		for(int i=0;i<ss.Length;i++)
		{	
			arr[i]=int.Parse(ss[i]);
		}
		int ret=0;
		int[]done=new int[num];
		for(int i=0;i<num;i++)
		{
			if(arr[i]==i || done[i]==1)continue;
			int count=0;
			int tt=i;
			while(true)
			{
				done[tt]=1;
				tt=arr[tt];
				if(tt==i)
				break;
				count++;
			}
			ret+=count;
		}
		Console.WriteLine(ret);
	}
}