Above described solution in python:

def solution(a):

    m = {}
    for i in range(len(a)):
        m[a[i]] = i 
        
    sorted_a = sorted(a)
    ret = 0
    
    for i in range(len(a)):
        if a[i] != sorted_a[i]:
            ret +=1
            
            ind_to_swap = m[ sorted_a[i] ]
            m[ a[i] ] = m[ sorted_a[i]]
            a[i],a[ind_to_swap] = sorted_a[i],a[i]
    return ret

raw_input()
a = [int(i) for i in raw_input().split(' ')]

asc=solution(list(a))
desc=solution(list(reversed(a)))
print min(asc,desc)

How does this algorithm deal with repeated elements?

Thank you for reverse. Min sum could be for ascent order as well as for decent order.

How to map in c without dictionaries??Direct addressing would take lot of storage which is dependant on values of the input sequence..?

could you pls explain why we reverse the list and run the same algorithm? i wrote a solution which is exactly same but I had not compared with the reversed list. So i was failing in some TCs. But i fail to see how sometimes reverse gives you the correct answer.

ur algo really helped me a lot...thank u..keep helping..

will this work if array has same entries, as key for a map MUST BE UNIQUE??

I used this logic, everything works but tests #1,#2,#3,#6 fail. Is there something special for these tests which needs to be handled & which is not mentioned in the threads?

CPP14 Implementation:

#include <iterator>
#include <map>

using namespace std;
#define FOR(i,n) for(long (i)=0;(i)<(n);((i)++))

int main() {
    map<long,long> iMap, iMap2;
    long iNum, index1, index2; cin >> iNum;
    index1=index2=0;
    long iArr[3][iNum];
    FOR(i,iNum){
        cin >> iArr[0][i];
        iMap[iArr[0][i]]=i;
    }
    iMap2=iMap;
    copy_n(iArr[0],iNum,iArr[1]);
    copy_n(iArr[0],iNum,iArr[2]);
    sort(iArr[1],iArr[1]+iNum);
    FOR(i,iNum){
        if(iArr[1][i]!=iArr[0][i]){
            index1++;
            iArr[0][iMap[iArr[1][i]]]=iArr[0][i];
            iMap[iArr[0][i]]=iMap[iArr[1][i]];
        }
        if(iArr[1][iNum-1-i]!=iArr[2][i]){
            index2++;
            iArr[2][iMap2[iArr[1][iNum-1-i]]]=iArr[2][i];
            iMap2[iArr[2][i]]=iMap2[iArr[1][iNum-1-i]];
        }
    }
    cout << min(index1,index2);
    return 0;
}

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.util.Collections.*;
public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        int n,count=0,count1=0;
        n= sc.nextInt();
         int []b= new int[n]; 
       Integer []a= new Integer[n]; 
        int []c= new int[n];
      HashMap map = new  HashMap();
       HashMap map1= new HashMap();
        for(int i=0;i<n;i++){
            int num=sc.nextInt();
            map.put(num,i);
            map1.put(num,i);
            a[i]=num;
            b[i]=num;
            c[i]=num;
        }
        
       Arrays.sort(a);
       
           for(int i=0;i<n;i++){
               if(a[i]!=b[i]){
                   count++;
                 int temp= b[(int) map.get(a[i])];
                   int x=b[(int) map.get(a[i])];
                  b[(int) map.get(a[i])]=b[i];
                   b[i]=temp;
                  map.put(b[(int) map.get(a[i])],(int) map.get(b[i]));
                   
               }
           }
        Arrays.sort(a,Collections.reverseOrder());
        for(int i=0;i<n;i++){
               if(a[i]!=c[i]){
                   count1++;
                 int temp= c[(int) map1.get(a[i])];
                   int x=c[(int) map1.get(a[i])];
                  c[(int) map1.get(a[i])]=c[i];
                   c[i]=temp;
                  map.put(c[(int) map1.get(a[i])],(int) map1.get(b[i]));
                   
               }
           }
        if(count1>count)
           System.out.println(count);
        else
             System.out.println(count1);
    }
}

Doesnt run for test case 2 3 and 9 Why???

"Then you need to execute it on input list and reversed input list - the smaller return value - is the answer." CAN YOU PLEASE EXPLAIN WHAT IS THIS LINE? I DIDNT GET IT

This approach in Ruby:

n = gets.to_i
a = gets.strip.split.map &:to_i
def find_swaps(a)
    map = a.each_with_index.map{|x,i| [x,i]}.to_h
    swaps = 0; sort = a.sort
    for i in 0...a.size do
        if sort[i] != a[i]
            swaps += 1
            map[a[i]] = map[sort[i]]
            a[map[sort[i]]], a[i] = a[i], sort[i] end end
    swaps end
puts [find_swaps(Marshal.load(Marshal.dump(a))),find_swaps(a.reverse)].min

I tried to implement your algorithm but I am getting half test cases as wrong answer. Can you help?

include

using namespace std;

int main() { int n; vectora; cin>>n; int u,temp1; maph; for(u=0;u>temp1; a.push_back(temp1); h[temp1]=u; } vectorb(a.begin(),a.end()); vectorc(a.begin(),a.end()); sort(b.begin(),b.end()); int count_a=0; int count_b=0; int i,j,sec; for(i=0;i()); for(i=0;i

I came up with a similar but not exactly the same approach in which i just counted mismatches and thought to apply some function on mismatches that would directly give swaps:

if mismatches%2:
    return mismatches//2 + 1
else:
    return mismatches//2

But it somehow fails test case 1, 2, 3, 6. In the end I decided to go with actually swapping and counting it

Isn't there any such function that could direcly be applied on mismatch count to yield number of swaps?

ackage algorithms.sorting;

import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner;

public class LilysHomework {

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] arr = new int[n];
    int[] sorted = new int[n];
    int[] reversed = new int[n];
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < n; i++){
        arr[i] = in.nextInt();
        sorted[i] = arr[i];
        reversed[i] = -arr[i];
        map.put(arr[i], i);
    }

    in.close();

    int[] diffs = new int[n];
    diffs[0] = 0;
    for(int i = 1; i < n; i++){
        diffs[i] = arr[i] - arr[0];
    }

    Arrays.sort(diffs);
    int pos = 0;
    int neg = 0;
    for(int diff : diffs){
        if(diff > 0){
            pos++;
        }
        if(diff < 0){
            neg++;
        }
    }

    boolean sortAscending = pos > neg;
    if(sortAscending){
        Arrays.sort(sorted);
    } else {
        Arrays.sort(reversed);
        for(int i = 0; i < n; i++){
            reversed[i] *= -1;
        }
        sorted = reversed;
    }

    int swaps = 0;
    for(int i = 0; i < n; i++){
        if(sorted[i] != arr[i]){
            swaps++;
            int target = map.get(sorted[i]);
            int temp = arr[target];
            arr[target] = arr[i];
            arr[i] = temp;
            map.put(arr[target], target);
        }
    }

    System.out.println(swaps);

    /*
    Prep stage:
    create map with:
    keys : values from input list,
    values : indexes of values from input list,
    make a copy of sorted input list

    Algo stage:
    Iterate through input list, and compare current value 
        (lets call it cv) against value from sorted list (lets call it scv). 
    If it is diffrent:
        increment number of swaps
        get index of the scv from map - map[scv],
        in input list swap cv with scv,
        update map[cv]=map[scv] (map[scv] does not need to be updated as we are not going to use it any more)
    */
}

} homeworkprosect

Thanks! for the reverse, from yesterday I was just seeing my code. Although, after using reverse I am still getting tc 1, 2, 3 , 4 failed :(

Great explanation, but it was a bit hard to follow without code to lean back on. This is my solution for JavaScript if anyone needs it (it was a b*tch to optimize...):

'use strict'

let input = ''

process.stdin.resume()
process.stdin.setEncoding('utf-8')
process.stdin.on('data', data => input += data)
process.stdin.on('end', () => main())

function main() {
    input = input.split('\n')
    let n = Number(input[0])
    let arr = input[1].split(' ').map(x => Number(x))
    let result = lilysHomework(n, arr)
    return console.log(result)
}

function lilysHomework (n, arr) {

    const swaps = (arr, sarr) => {
        let [s, idx] = [0, []]
        arr.forEach((v,i) => idx[v] = i)
        for (let i = 0, j; i < n; i++) {
            while (arr[i] === sarr[i] && i < n) i++
            j = idx[sarr[i]]
            idx[arr[i]] = j
            arr[i] = [ arr[j], arr[j] = arr[i] ][0]
            s++
        }
        return s-1
    }

    let asc = [...arr].sort((a,b) => a-b)
    let desc = [...asc].reverse()
    let s1 = swaps([...arr], asc)
    let s2 = swaps(arr, desc)

    return Math.min(s1, s2)
}

I found another way to achieve the objective, this problem is very close to the minimum swaps problem, wich the objective is count the minimum swaps to sort a array (https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/):

from collections import defaultdict

def swaps(arr_e):
        vis = defaultdict(bool)
        ans = 0
        j = 0
        for i in range(len(arr_e)):
                if vis[i] or arr_e[i][0] == i:
                        continue

                j = i
                cycles = 0
                while not vis[j]:
                        vis[j] = True
                        j = arr_e[j][0]
                        cycles += 1

                if cycles > 0:
                        ans += cycles - 1

        return ans

# Complete the lilysHomework function below.
def lilysHomework(arr):
        arr_e = list(enumerate(arr))
        arr_s = sorted(arr_e, key=lambda x: x[1])
        ans1 = swaps(arr_s)
        arr_s = sorted(arr_e, key=lambda x: x[1], reverse = True)
        ans2 = swaps(arr_s)

        return min(ans1, ans2)

C++ solution :

int lilysHomework(vector<int>& arr) {
    vector<int> temp = arr, sorted = arr;
    sort(sorted.begin(), sorted.end());
    unordered_map<int, int> m, mtemp;
    int count, count1=0, count2=0;
    for (int i=0;i<arr.size();i++)  m[arr[i]]=i;
    mtemp=m;

    for (int i=0;i<sorted.size();i++)
        if (sorted[i]!=arr[i])
        {
            count1++;
            swap(arr[i], arr[m[sorted[i]]]);
            m[arr[m[sorted[i]]]]=m[sorted[i]];
        }
    reverse(sorted.begin(), sorted.end());
    arr=temp;
    m=mtemp;
    for (int i=0;i<sorted.size();i++)
        if (sorted[i]!=arr[i])
        {
            count2++;
            swap(arr[i], arr[m[sorted[i]]]);
            m[arr[m[sorted[i]]]]=m[sorted[i]];
        }
    return count=min(count1, count2);
}

for 0<=i if they are not equal increment s. s-1 would be the answer.
i.e, no.of elements that are not in right place - 1

Thanks mate. Nice algo. I didn't understand it at first, but then I solved it using pen and paper using this algo and then got the gist of it.

The idea is to sort the given array and then compare each element of the given array with the sorted array . If the elements in the given array don't match move the offending element to the position of the correct element and bring the correct element in the the position of the offending element. And using a hashmap to store the indexes for O(1) lookup. Ofcourse this works because there are no duplicate elements in the given array.

Cheers!

Hi, I tried the above solution. However, I have some doubt. m[a[i]] = m[s[i]] a[i], a[m[s[i]]] = s[i], a[i] In the above code snippet, I had earlier tried with these two sentences swapped, which didn't give me a correct answer. I am not able to understand why swapping these statements made a difference. Can you please give me insights on this?

I have done the same thing but still i am not getting the answer

int lilysHomework(vector<int> arr) {
    int swaps=0;
    vector<int> sorted;
    sorted=arr;
    sort(sorted.begin(),sorted.end());
    map<int,int> count;
    for(int i=0;i<arr.size();i++)
        count[arr[i]]=i;

    for(int i=0;i<arr.size();i++){
        if(arr[i]!=sorted[i]){
            swaps++;
            int temp1=arr[i],temp2=sorted[i];
            swap(arr[i],arr[count[temp2]]);
            count[temp1]=count[temp2];
        }
    }

    return swaps;
}

For the input

3 4 2 5 1

I am doing these swaps

1 4 2 5 3 
1 2 4 5 3 
1 2 3 5 4 
1 2 3 4 5

Total swaps here are 4 but the expected outcome is 2

What am I doing wrong here?

:) Same thing I was thinking!

Great, thank you for the help, I will check it later!

hey, if the numbers in the unsorted array are not serial then what do we do? for example: original array: 72 3 0 4 1 6 5 2 thanks

You explained it very nicely .... Thank u so much for helping me...

Hey, counter example here:

5
3 4 2 1 5

the expected output is 3, but with your logic:

3 4 2 1 5
1 2 3 4 5
---------
1 1 1 1 0

&&

3 4 2 1 5
5 4 3 2 1
---------
1 0 1 1 1

the output is ceil(4/2) = 2

The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.

my solution handles duplicates elements its not really challenging.

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

I tried the same but i think its because quicksorting takes a lot of time to partition and then recounting them takes a lot of time

I got it to run with quicksort. What helped me was to remember to operate on copies of the arrays, since the approach of comparing with sorted and swapping elements destroys the map and the original input array. You need to compare for both asc and desc. One is just inversion of the other. Here is my C# verion with custom quick sort.

// Complete the lilysHomework function below.
static int lilysHomework(int[] arr) {
    var originalIndexValueMap = new Dictionary<int, int>();
    for (var i = 0; i < arr.Length; i++)
    {
        originalIndexValueMap[arr[i]] = i;
    }

    var sortedAsc = new int[arr.Length];
    Array.Copy(arr, 0, sortedAsc, 0, arr.Length);
    quicksort(sortedAsc, 0, arr.Length - 1);

    var sortedDesc = new int[arr.Length];
    Array.Copy(sortedAsc, 0, sortedDesc, 0, sortedAsc.Length);
    Array.Reverse(sortedAsc);

    var ascCount = Count(arr, sortedAsc, originalIndexValueMap);
    var descCount = Count(arr, sortedDesc, originalIndexValueMap);

    return Math.Min(ascCount, descCount);
}

static int Count(int[] a, int[] sorted, Dictionary<int, int> map)
{
    var arr = new int[a.Length];
    Array.Copy(a, 0, arr, 0, arr.Length);

    var mapCopy = new Dictionary<int, int>();
    foreach (var kv in map)
    {
        mapCopy[kv.Key] = kv.Value;
    }

    var count = 0;
    for (var i = 0; i < arr.Length; i++)
    {
        if (arr[i] != sorted[i])
        {
            count++;
            var indexToSwap = mapCopy[sorted[i]];
            mapCopy[arr[i]] = indexToSwap;

            var tmp = arr[i];
            arr[i] = arr[indexToSwap];
            arr[indexToSwap] = tmp;
        }
    }

    return count;
}

static void quicksort(int[] arr, int left, int right)
{
    var p = arr[(right + left) / 2];
    int i = left;
    int j = right;
    while (i <= j)
    {
        while (arr[i] < p) {
            i++;
        }

        while (arr[j] > p) {
            j--;
        }

        if (i <= j)
        {
            var tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }

    if (left < j)
    {
        quicksort(arr, left, j);
    }

    if (right > i)
    {
        quicksort(arr, i, right);
    }
}