HackerRank Lily’s Homework problem solution

#!/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))

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)));

    }
}

 
#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;
}