In this HackerRank Minimum swaps 2 interview preparation kit problem solution You are given an unordered array consisting of consecutive integers [1, 2, 3, …, n] without any duplicates. You are allowed to swap any two elements. You need to find the minimum number of swaps required to sort the array in ascending order.
Problem solution in Python programming.
#!/bin/python3
import math
import os
import random
import re
import sys
# Complete the minimumSwaps function below.
def minimumSwaps(arr):
temp = [0] * (len(arr) + 1)
for pos, val in enumerate(arr):
temp[val] = pos
pos += 1
swaps = 0
for i in range(len(arr)):
if arr[i] != i+1:
swaps += 1
t = arr[i]
arr[i] = i+1
arr[temp[i+1]] = t
temp[t] = temp[i+1]
return swaps
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
n = int(input())
arr = list(map(int, input().rstrip().split()))
res = minimumSwaps(arr)
fptr.write(str(res) + 'n')
fptr.close()
Problem solution in Java Programming.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class Solution {
// Complete the minimumSwaps function below.
static int minimumSwaps(int[] arr) {
int i =0;
int count=0;
int temp;
int n = arr.length;
while(i<n){
if(arr[i] != i+1){
temp = arr[i];
arr[i] = arr[temp-1];
arr[temp-1]=temp;
count++;
}
else{
i++;
}
}
return count;
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int n = scanner.nextInt();
scanner.skip("(rn|[nru2028u2029u0085])?");
int[] arr = new int[n];
String[] arrItems = scanner.nextLine().split(" ");
scanner.skip("(rn|[nru2028u2029u0085])?");
for (int i = 0; i < n; i++) {
int arrItem = Integer.parseInt(arrItems[i]);
arr[i] = arrItem;
}
int res = minimumSwaps(arr);
bufferedWriter.write(String.valueOf(res));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
Problem solution in C++ programming.
#include<bits/stdc++.h> using namespace std; int a[100005]; bool visited[100005]; int solve(int n) { pair<int, int> p[n]; for (int i = 0; i < n; i++) { p[i].first = a[i]; // Storing the original position of a[i] p[i].second = i; } sort(p, p+n); int ans = 0; for (int i = 0; i < n; i++) { //visited[i]=true indicates that index i belongs to a cycle that is already counted //p[i].second = i denotes that the ith element was at its correct position if (visited[i] || p[i].second == i) continue; int cycle_size = 0; int j = i; //Counting the size of the cycle while (!visited[j]) { visited[j] = 1; j = p[j].second; cycle_size++; } ans += (cycle_size - 1); } return ans; } int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); } int ans = solve(n); printf("%dn", ans); return 0; }
timeout in hacker rank for test cases with input length 100000
in javascript
This comment has been removed by the author.