Given an array of N distinct positive integers. The task is to find the minimum cost to sort the given array. The cost of swapping two elements X and Y is X*Y.
Examples:
Input: arr[] = {8, 4, 5, 3, 2, 7}
Output: 57
Explanation:
Swap element at index 4 with index 5 – cost(arr[4]*arr[5]) = (2*7) = 14,
Array becomes {8, 4, 5, 3, 7, 2}
then, swap element at index 0 with 5 – cost(arr[0]*arr[5]) = (8*2) = 16,
Array becomes {2, 4, 5, 3, 7, 8}
then, swap element at index 2 with 3 – cost(arr[2]*arr[3]) = (5*3) = 15,
Array becomes {2, 4, 3, 5, 7, 8}
then, swap element at index 1 with 2 – cost(arr[1]*arr[2]) = (4*3) = 12,
Array becomes {2, 3, 4, 5, 7, 8}
Array is now sorted and total cost = 14+16+15+12 = 57.Input: arr[] = {1, 8, 9, 7, 6}
Output: 36
Approach: The idea is that for sorting a cycle we have two choices either to use only the local minimum of the cycle or to use both local and overall minimum of the array. Choose the one swap element that gives a lower cost. Below are the steps:
- Calculate the local minimum (say local_minimum) which is the minimum element in the present cycle and the overall minimum (say overall_minimum) which is the minimum element in the whole array.
- Calculate and store the cost to sort the cycle (say cost1) by using only local minimum value.
- Also, calculate and store the cost to sort the cycle (say cost2) by using both local minimum value and the overall minimum value.
- Now the minimum cost to sort this cycle will be minimum of the costs cost1 and cost2. Add this cost to the total cost.
Below is the illustration for the array arr[] = {1, 8, 9, 7, 6}:
- In the above figure, cycle {8, 9, 7, 6} can be sorted using the local minimum element 6 or with overall minimum element 1. By using only local minimum element i.e., swap 6 and 9, swap 6 and 7, swap 6 and 8. Therefore, the total cost is 6*9 + 6*7 + 6*8 = 144.
- By using both overall minimum and local minimum element i.e., swap 1 and 6, swap 1 and 9, swap 1 and 7, swap 1 and 8, swap 1 and 6. Therefore, the total cost is 1*6 +1*9 +1*7 +1*8 +1*6 = 36.
- The minimum of the above cost is 36.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function returns the minimum cost// to sort the given arrayint minCost(int arr[], int n){ // Create array of pairs in which // 1st element is the array element // and 2nd element is index of first pair<int, int> sorted[n]; // Initialize the total cost int total_cost = 0; for (int i = 0; i < n; i++) { sorted[i].first = arr[i]; sorted[i].second = i; } // Sort the array with respect to // array value sort(sorted, sorted + n); // Initialize the overall minimum // which is the 1st element int overall_minimum = sorted[0].first; // To keep track of visited elements // create a visited array & initialize // all elements as not visited bool vis[n] = { false }; // Iterate over every element // of the array for (int i = 0; i < n; i++) { // If the element is visited or // in the sorted position, and // check for next element if (vis[i] && sorted[i].second == i) continue; // Create a vector which stores // all elements of a cycle vector<int> v; int j = i; // It covers all the elements // of a cycle while (!vis[j]) { vis[j] = true; v.push_back(sorted[j].first); j = sorted[j].second; } // If cycle is found then the // swapping is required if (v.size() > 0) { // Initialize local minimum with // 1st element of the vector as // it contains the smallest // element in the beginning int local_minimum = v[0], result1 = 0, result2 = 0; // Stores the cost with using only // local minimum value. for (int k = 1; k < v.size(); k++) result1 += (local_minimum * v[k]); // Stores the cost of using both // local minimum and overall minimum for (int k = 0; k < v.size(); k++) result2 += (overall_minimum * v[k]); // Update the result2 result2 += (overall_minimum * local_minimum); // Store the minimum of the // two result to total cost total_cost += min(result1, result2); } } // Return the minimum cost return total_cost;}// Driver Codeint main(){ // Given array arr[] int arr[] = { 1, 8, 9, 7, 6 }; int n = (sizeof(arr) / sizeof(int)); // Function Call cout << minCost(arr, n); return 0;} |
Java
// Java program to implement // the above approach import java.util.*;class GFG{ // Function returns the minimum cost // to sort the given array static int minCost(int arr[], int n) { // Create array of pairs in which // 1st element is the array element // and 2nd element is index of first int[][] sorted = new int[n][2]; // Initialize the total cost int total_cost = 0; for(int i = 0; i < n; i++) { sorted[i][0] = arr[i]; sorted[i][1] = i; } // Sort the array with respect to // array value Arrays.sort(sorted, (a, b) -> a[0] - b[0]); // Initialize the overall minimum // which is the 1st element int overall_minimum = sorted[0][0]; // To keep track of visited elements // create a visited array & initialize // all elements as not visited boolean[] vis = new boolean[n]; // Iterate over every element // of the array for(int i = 0; i < n; i++) { // If the element is visited or // in the sorted position, and // check for next element if (vis[i] && sorted[i][1] == i) continue; // Create a vector which stores // all elements of a cycle ArrayList<Integer> v = new ArrayList<>(); int j = i; // It covers all the elements // of a cycle while (!vis[j]) { vis[j] = true; v.add(sorted[j][0]); j = sorted[j][1]; } // If cycle is found then the // swapping is required if (v.size() > 0) { // Initialize local minimum with // 1st element of the vector as // it contains the smallest // element in the beginning int local_minimum = v.get(0), result1 = 0, result2 = 0; // Stores the cost with using only // local minimum value. for(int k = 1; k < v.size(); k++) result1 += (local_minimum * v.get(k)); // Stores the cost of using both // local minimum and overall minimum for(int k = 0; k < v.size(); k++) result2 += (overall_minimum * v.get(k)); // Update the result2 result2 += (overall_minimum * local_minimum); // Store the minimum of the // two result to total cost total_cost += Math.min(result1, result2); } } // Return the minimum cost return total_cost; } // Driver codepublic static void main (String[] args) { // Given array arr[] int arr[] = { 1, 8, 9, 7, 6 }; int n = arr.length; // Function call System.out.print(minCost(arr, n)); }}// This code is contributed by offbeat |
Python3
# Python3 program for the above approach # Function returns the minimum cost # to sort the given array def minCost(arr, n): # Create array of pairs in which # 1st element is the array element # and 2nd element is index of first sortedarr = [] # Initialize the total cost total_cost = 0 for i in range(n): sortedarr.append([arr[i], i]) # Sort the array with respect to # array value sortedarr.sort() # Initialize the overall minimum # which is the 1st element overall_minimum = sortedarr[0][0] # To keep track of visited elements # create a visited array & initialize # all elements as not visited vis = [False] * n # Iterate over every element # of the array for i in range(n): # If the element is visited or # in the sorted position, and # check for next element if vis[i] and sortedarr[i][1] == i: continue # Create a vector which stores # all elements of a cycle v = [] j = i size = 0 # It covers all the elements # of a cycle while vis[j] == False: vis[j] = True v.append(sortedarr[j][0]) j = sortedarr[j][1] size += 1 # If cycle is found then the # swapping is required if size != 0: # Initialize local minimum with # 1st element of the vector as # it contains the smallest # element in the beginning local_minimum = v[0] result1 = 0 result2 = 0 # Stores the cost with using only # local minimum value. for k in range(1, size): result1 += local_minimum * v[k] # Stores the cost of using both # local minimum and overall minimum for k in range(size): result2 += overall_minimum * v[k] # Update the result2 result2 += (overall_minimum * local_minimum) # Store the minimum of the # two result to total cost total_cost += min(result1, result2) # Return the minimum cost return total_cost# Driver code# Given array arr[] A = [ 1, 8, 9, 7, 6 ]# Function call ans = minCost(A, len(A))print(ans)# This code is contributed by kumarkashyap |
C#
using System;using System.Collections.Generic;class GFG{ // Function returns the minimum cost // to sort the given array static int minCost(int[] arr, int n) { // Create array of pairs in which // 1st element is the array element // and 2nd element is index of first int[][] sorted = new int[n][]; // Initialize the total cost int total_cost = 0; for (int i = 0; i < n; i++) { sorted[i] = new int[2]; sorted[i][0] = arr[i]; sorted[i][1] = i; } // Sort the array with respect to // array value Array.Sort(sorted, (a, b) => a[0] - b[0]); // Initialize the overall minimum // which is the 1st element int overall_minimum = sorted[0][0]; // To keep track of visited elements // create a visited array & initialize // all elements as not visited bool[] vis = new bool[n]; // Iterate over every element // of the array for (int i = 0; i < n; i++) { // If the element is visited or // in the sorted position, and // check for next element if (vis[i] && sorted[i][1] == i) continue; // Create a vector which stores // all elements of a cycle List<int> v = new List<int>(); int j = i; // It covers all the elements // of a cycle while (!vis[j]) { vis[j] = true; v.Add(sorted[j][0]); j = sorted[j][1]; } // If cycle is found then the // swapping is required if (v.Count > 0) { // Initialize local minimum with // 1st element of the vector as // it contains the smallest // element in the beginning int local_minimum = v[0], result1 = 0, result2 = 0; // Stores the cost with using only // local minimum value. for (int k = 1; k < v.Count; k++) result1 += (local_minimum * v[k]); // Stores the cost of using both // local minimum and overall minimum for (int k = 0; k < v.Count; k++) result2 += (overall_minimum * v[k]); // Update the result2 result2 += (overall_minimum * local_minimum); // Store the minimum of the // two result to total cost total_cost += Math.Min(result1, result2); } } // Return the minimum cost return total_cost; } // Driver code public static void Main(String[] args) { // Given array arr[] int[] arr = {1, 8, 9, 7, 6}; var n = arr.Length; // Function call Console.Write(GFG.minCost(arr, n)); }} |
Javascript
<script>// JavaScript program for the above approach// Function returns the minimum cost// to sort the given arrayfunction minCost(arr, n){ // Create array of pairs in which // 1st element is the array element // and 2nd element is index of first let sortedarr = [] // Initialize the total cost let total_cost = 0 for(let i = 0; i < n; i++){ sortedarr.push([arr[i], i]) } // Sort the array with respect to // array value sortedarr.sort() // Initialize the overall minimum // which is the 1st element let overall_minimum = sortedarr[0][0] // To keep track of visited elements // create a visited array & initialize // all elements as not visited let vis = new Array(n).fill(false) // Iterate over every element // of the array for(let i = 0; i < n; i++){ // If the element is visited or // in the sorted position, and // check for next element if(vis[i] && sortedarr[i][1] == i) continue // Create a vector which stores // all elements of a cycle let v = [] let j = i let size = 0 // It covers all the elements // of a cycle while(vis[j] == false){ vis[j] = true v.push(sortedarr[j][0]) j = sortedarr[j][1] size += 1 } // If cycle is found then the // swapping is required if(size != 0){ // Initialize local minimum with // 1st element of the vector as // it contains the smallest // element in the beginning let local_minimum = v[0] let result1 = 0 let result2 = 0 // Stores the cost with using only // local minimum value. for(let k = 1; k < size; k++) result1 += local_minimum * v[k] // Stores the cost of using both // local minimum and overall minimum for(let k = 0; k < size; k++) result2 += overall_minimum * v[k] // Update the result2 result2 += (overall_minimum * local_minimum) // Store the minimum of the // two result to total cost total_cost += Math.min(result1, result2) } } // Return the minimum cost return total_cost}// Driver code// Given array arr[]A = [ 1, 8, 9, 7, 6 ]// Function callans = minCost(A, A.length)document.write(ans,"</br>")// This code is contributed by shinjanpatra</script> |
Output:
36
Time Complexity: O(N*log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
