Minimum cost to sort an Array such that swapping X and Y costs XY | Java program to implement the above approach ; Function returns the minimum cost to sort the given array ; Create array of pairs in which 1 st element is the array element and 2 nd element is index of first ; Initialize the total cost ; Sort the array with respect to array value ; Initialize the overall minimum which is the 1 st element ; To keep track of visited elements create a visited array & initialize all elements as not visited ; Iterate over every element of the array ; If the element is visited or in the sorted position , and check for next element ; Create a vector which stores all elements of a cycle ; It covers all the elements of a cycle ; If cycle is found then the swapping is required ; Initialize local minimum with 1 st element of the vector as it contains the smallest element in the beginning ; Stores the cost with using only local minimum value . ; Stores the cost of using both local minimum and overall minimum ; Update the result2 ; Store the minimum of the two result to total cost ; Return the minimum cost ; Driver code ; Given array arr [ ] ; Function call
import java . util . * ; class GFG { static int minCost ( int arr [ ] , int n ) { int [ ] [ ] sorted = new int [ n ] [ 2 ] ; int total_cost = 0 ; for ( int i = 0 ; i < n ; i ++ ) { sorted [ i ] [ 0 ] = arr [ i ] ; sorted [ i ] [ 1 ] = i ; } Arrays . sort ( sorted , ( a , b ) -> a [ 0 ] - b [ 0 ] ) ; int overall_minimum = sorted [ 0 ] [ 0 ] ; boolean [ ] vis = new boolean [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] && sorted [ i ] [ 1 ] == i ) continue ; ArrayList < Integer > v = new ArrayList < > ( ) ; int j = i ; while ( ! vis [ j ] ) { vis [ j ] = true ; v . add ( sorted [ j ] [ 0 ] ) ; j = sorted [ j ] [ 1 ] ; } if ( v . size ( ) > 0 ) { int local_minimum = v . get ( 0 ) , result1 = 0 , result2 = 0 ; for ( int k = 1 ; k < v . size ( ) ; k ++ ) result1 += ( local_minimum * v . get ( k ) ) ; for ( int k = 0 ; k < v . size ( ) ; k ++ ) result2 += ( overall_minimum * v . get ( k ) ) ; result2 += ( overall_minimum * local_minimum ) ; total_cost += Math . min ( result1 , result2 ) ; } } return total_cost ; } public static void main ( String [ ] args ) { int arr [ ] = { 1 , 8 , 9 , 7 , 6 } ; int n = arr . length ; System . out . print ( minCost ( arr , n ) ) ; } }