HackerRank Lily's Homework problem solution

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("%d\n", res);
    return 0;
}