Minimum cost to sort an Array such that swapping X and Y costs XY | 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 ; Given array arr [ ] ; Function call
def minCost ( arr , n ) : NEW_LINE INDENT sortedarr = [ ] NEW_LINE total_cost = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT sortedarr . append ( [ arr [ i ] , i ] ) NEW_LINE DEDENT sortedarr . sort ( ) NEW_LINE overall_minimum = sortedarr [ 0 ] [ 0 ] NEW_LINE vis = [ False ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT if vis [ i ] and sortedarr [ i ] [ 1 ] == i : NEW_LINE INDENT continue NEW_LINE DEDENT v = [ ] NEW_LINE j = i NEW_LINE size = 0 NEW_LINE while vis [ j ] == False : NEW_LINE INDENT vis [ j ] = True NEW_LINE v . append ( sortedarr [ j ] [ 0 ] ) NEW_LINE j = sortedarr [ j ] [ 1 ] NEW_LINE size += 1 NEW_LINE DEDENT if size != 0 : NEW_LINE INDENT local_minimum = v [ 0 ] NEW_LINE result1 = 0 NEW_LINE result2 = 0 NEW_LINE for k in range ( 1 , size ) : NEW_LINE INDENT result1 += local_minimum * v [ k ] NEW_LINE DEDENT for k in range ( size ) : NEW_LINE INDENT result2 += overall_minimum * v [ k ] NEW_LINE DEDENT result2 += ( overall_minimum * local_minimum ) NEW_LINE total_cost += min ( result1 , result2 ) NEW_LINE DEDENT DEDENT return total_cost NEW_LINE DEDENT A = [ 1 , 8 , 9 , 7 , 6 ] NEW_LINE ans = minCost ( A , len ( A ) ) NEW_LINE print ( ans ) NEW_LINE