In this HackerRank Lily’s Homework problem solution we have given the array arr, determine and return the minimum number of swaps that should be performed in order to make the array beautiful.
Problem solution in Python.
#!/bin/python3 import math import os import random import re import sys # # Complete the 'lilysHomework' function below. # # The function is expected to return an INTEGER. # The function accepts INTEGER_ARRAY arr as parameter. # n = int(input()) l = list(map(int, input().split())) sort = sorted(l) rev = list(reversed(l)) d = {} for i in range(n): if sort[i] not in d: d[sort[i]] = i swaps = 0 i = 0 while i < n: if sort[i] == l[i]: i += 1 continue swaps += 1 l[d[l[i]]], l[i] = l[i], l[d[l[i]]] d[sort[i]] += 1 d = {} for i in range(n): if sort[i] not in d: d[sort[i]] = i swaps_rev = 0 i = 0 while i < n: if sort[i] == rev[i]: i += 1 continue swaps_rev += 1 rev[d[rev[i]]], rev[i] = rev[i], rev[d[rev[i]]] d[sort[i]] += 1 print(min(swaps, swaps_rev))
Problem solution in Java.
import java.io.*; import java.math.*; import java.security.*; import java.text.*; import java.util.*; import java.util.concurrent.*; import java.util.function.*; import java.util.regex.*; import java.util.stream.*; import static java.util.stream.Collectors.joining; import static java.util.stream.Collectors.toList; import java.util.stream.IntStream; public class LilysHomework { private static final Scanner scn = new Scanner(System.in); private static void swap(long[] array, int index1, int index2) { long temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } private static int swaps(long[] unsortedValues) { int swaps = 0; Map<Long, Integer> locations = new HashMap<>(); for (int i = 0; i < unsortedValues.length; i++) { locations.put(unsortedValues[i], i); } long [] sortedValue = unsortedValues.clone(); Arrays.sort(sortedValue); for (int i = 0; i < sortedValue.length; i++) { if (sortedValue[i] != unsortedValues[i]) { swaps++; int swapIndex = locations.get(sortedValue[i]); locations.put(unsortedValues[i], swapIndex); swap(unsortedValues, i, swapIndex); } } return swaps; } public static void main(String[] args) { int numberOfElements = scn.nextInt(); long[] values = new long[numberOfElements]; for (int i = 0; i < numberOfElements; i++) { int value = scn.nextInt(); values[i] = value; } // When all you have is a hammer, everything begins to look like a nail. long [] reverseValue = IntStream.rangeClosed(1, values.length).mapToLong( i -> values[values.length - i]).toArray(); System.out.println(Math.min(swaps(values), swaps(reverseValue))); } }
Problem solution in C++.
#include <bits/stdc++.h> const int N = int(1e5) + 5; int n, a[N], p[N]; bool used[N]; bool cmp(int i, int j) { return a[i] < a[j]; } int solve() { memset(used, 0, sizeof(used)); int cur = 0; for (int i = 0; i < n; ++i) { int x = i; if (used[x]) continue; while (!used[x]) { used[x] = true; x = p[x]; } cur++; } return n - cur; } int main() { assert(scanf("%d", &n) == 1); for (int i = 0; i < n; ++i) { assert(scanf("%d", &a[i]) == 1); assert(1 <= a[i] && a[i] <= int(2e9)); p[i] = i; } std::sort(p, p + n, cmp); for (int i = 0; i + 1 < n; ++i) assert(a[p[i]] != a[p[i + 1]]); int res = solve(); std::reverse(p, p + n); res = std::min(res, solve()); printf("%dn", res); return 0; }
Maybe I am missing something but I think this is not quite correct..
long [] reverseValue = IntStream.rangeClosed(1, values.length).mapToLong(
i -> values[values.length – i]).toArray();
System.out.println(Math.min(swaps(values), swaps(reverseValue)));
providing "values" and "reverseValue" arrays as parameters to "swaps" method is the same thing.. both of them are sorted to the same array in the "swaps" method.. I think the idea was to do a reverse sort (descending) INSIDE the "swaps" method..