I've done it :) Passing all test :) My approach is:

Prep stage:

1. create map with:
   • keys : values from input list,
   • values : indexes of values from input list,
2. 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)

Then you need to execute it on input list and reversed input list - the smaller return value - is the answer.

Time complexity is equal to sort time complexity (usually O(n logn) ). Space O(n)

Finally solved it! Spent some time trying to figure out the hidden details. Would appreciate if there had been another test case. Things i learnt - Java specifics (might be useful if you're stuck):

1. You have to sort the array in both ascending and descending order as both will yield a minimum sum.
2. Remember to use a LinkedHashMap (if you are using one) and not a HashMap to store the element key and index value (to preserve insertion order).
3. A copy of an ArrayList is a shallow copy. You need to addAll(originalArray) to create another array with the same values as the originalArray.

The algorithm is pretty simple: (just a brief run-through , note the details, figure out the implementation)

• compare every element of original array with a copy of the sorted array (refer 3)
• when there's a mismatch, swap elements into their respective positions
• count the total number of swaps
• repeat the above with the array reversed (refer 1)
• use a hashmap as a cache/lookup to speed things up O(1) (refer 2).

Example:

7 3 0 4 1 6 5 2 - original array

0 1 2 3 4 5 6 7 - sorted array

0 3 7 4 1 6 5 2 - after first swap

0 1 7 4 3 6 5 2 - after second swap

0 1 2 4 3 6 5 7 - after third swap

0 1 2 3 4 6 5 7 - after fourth swap

0 1 2 3 4 5 6 7 - after fifth swap

Did you notice the pattern? All the best!

Problem could be intresting if you try to solve it for array having duplicate elements.

Have to compare ascending/descending order because we have to get minimum swap count.

They have different swap count so you have to print smaller one.

I used cycle algorithm for counting it.

you can reference below site.

http://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/

In this problem, my intuition was telling me to just count the different positions between the input array and the sorted input array and then divide this count between 2 rounding up. For example: input array: 1 5 3 4 sorted array: 1 3 4 5 count: 0 1 1 1 = 3 number of swaps = ceil(3/2) = 2

In all the cases that I have tried I get the correct answer. I take into account normal and reverse order. However, test cases #1,#2,#3,#6 give me a wrong answer. Could someone tell me the problem in my reasoning or give me a counter example?

I thought I could solve this problem by quicksorting the array and then counting the number of swaps.

No other person did it this way and I was unable to get it to pass for more than the first test case. I guess I misunderstood the problem somehow.

Why wouldn't my approach work?

import java.io.; import java.util.;

public class Solution {

 static int size;

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 input=new Scanner(System.in);

    size=input.nextInt();

    //used for ascending order
    Integer ar[]=new Integer[size];

    // this will be used for decending array
    Integer copy_ar[]=new Integer[size];

    //store sorted array
    Integer sort_ar[]=new Integer[size];

    // store the index of array
    HashMap <Integer,Integer> map=new HashMap<>();
    HashMap <Integer,Integer> desMap=new HashMap<>();
    int ascOrder,desOrder;
    for(int index=0;index<size;index++)
    {

       ar[index]=input.nextInt();

        map.put(ar[index],index);
    }


    desMap.putAll(map);
    copy_ar=ar.clone();
    sort_ar=ar.clone();
    Arrays.sort(sort_ar);


     ascOrder=countSwap(ar,map,sort_ar);
    Arrays.sort(sort_ar, Collections.reverseOrder());

    desOrder=countSwap(copy_ar,desMap,sort_ar);

    if(ascOrder<desOrder)
    {System.out.println(ascOrder);}
    else
    {
        System.out.println(desOrder);
    }
}


public static int countSwap(Integer ar[],HashMap<Integer,Integer> map,Integer sort_ar[])
{

    int count=0;
    int swapIndex;

    for(int index=0;index<size;index++)
    {


        if(sort_ar[index]!=ar[index])
        {
            swapIndex=map.get(sort_ar[index]);


            map.put(sort_ar[index],index);
            map.put(ar[index],swapIndex);
            ar[swapIndex]=ar[index];
            ar[index]=sort_ar[index];
            count++;
        }

    }
 //   System.out.println(map);

    return count;

}

}

My C++ Solution, Passing all test Cases :D

#include <bits/stdc++.h>

using namespace std;

int lilysHomework(vector <int> arr, vector<int> asc, vector<int>des, int length, map <int, int> maps) 
    {
    int swaps = 0;
        map<int, int> :: iterator it;
        for(int i=0; i<length; i++)
            {
                if(asc[i] != arr[i])
                {
                    //find the index of the element from the map
                    it = maps.find(asc[i]);
                    int index = it->second;
                    swap(arr[i], arr[index]); //swap performed
                    
                    //updating the maps value
                    it = maps.find(arr[index]);
                    it->second = index;
                    swaps+=1;
                }
        }
    return swaps;
    }


int main() {
    int n;
    cin >> n;
    map <int, int> maps;
     
    vector<int> arr(n);
    vector<int> asc(n);
    vector<int> des(n);
    
    for(int arr_i = 0; arr_i < n; arr_i++){
       cin >> arr[arr_i];
       maps.insert(pair <int, int> (arr[arr_i], arr_i));
    }
    
    asc = arr;
    des = arr;
    
    sort(asc.begin(), asc.end());
    sort(des.begin(), des.end(), greater<int>());
    
    //Finding the swaps by comparing input data array withascending Sorted array
    int result = lilysHomework(arr, asc, des, n, maps);

    //Finding the swaps by comparing the input data array with Descending sorted array
    maps.clear(); //Reset the maps
    for(int i=0; i<n; i++)
        maps.insert(pair <int, int> (arr[i], i));
    int result2 = lilysHomework(arr, des, asc, n, maps);
    
    cout<<min(result, result2)<<endl;
    return 0;
}

Help! What's the problem with my code? I can't pass the test cases. int lilysHomework(vector arr) { // Complete this function long min=INT_MAX, cnt=0,idx=0; for(long i=0;i

int n; 
    cin >> n;
    vector<pair<long long,int> > v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i].first;
        v[i].second = i;
    }
    sort(v.begin(),v.end(),comp);
    int count = 0; 
    for(int j = 0; j < n; j++){
        if(v[j].second!=j){
            int x;
            for(int i = j+1; i < n; i++){
                if(v[i].second==j){
                    x = i; break;
                }
            }  
            v[x].second = v[j].second;
            v[j].second = j;
            count++;
        }
    }
    cout << count;

Why the above code is not passing all test cases? this code simple checks the index of element with the rank after sorting and if it don't matches with the rank just find the element with index of the rank and swap the index values of both