Minimize cost to convert Array into permutation by removing or inserting Integers
Given an array arr[] of size N, the task is to find the minimum cost required to convert a given array into a permutation from 1 to M (where M can be any positive value) by performing the following operations:
- You can remove any integer from the given array with cost X.
- You can insert any integer in the array at any position with cost Y.
Examples:
Input: arr = { 2, 1, 3, 6, 7 }, X = 2, Y = 3
Output: 4
Explanation: Remove the number 6 and 7 from the array that take 2 + 2 cost.Input: arr = { 2, 3, 6, 3, 5 }, X = 3, Y =7
Output: 16
Explanation: Remove the number 3, 5, 6 that take cost 3 + 3 + 3 = 9 and add number 1 take cost 7. So total cost = 9 + 7.
Approach: To solve the problem follow the below idea:
Initially keep the distinct values in a temporary array (say temp[] of size M), sort the array and traverse from left. Consider, we want the permutation to have values from 1 to the value of ith index. Consider the cost required in this manner for each index and the minimum of them will be required answer.
So, the cost for ith index will be (M – i – 1)*X + (temp[i] – (i + 1)) * Y because we have to remove (M – (i + 1)) elements and insert (temp[i] -(i+1)) new elements.
Illustration:
For a better understanding, follow the below illustration:
Consider arr[] = { 2, 3, 6, 3, 5 }, X = 3, Y =7
First create an array with only distinct elements temp[] and sort it. So temp[] will be {2, 3, 5, 6}. So initially we have already taken a cost of 3 to remove the duplicate
Index 0: Remove all numbers after index 0, it takes cost 3 * 3 for remove and add [2 – (0+1)] = 1 new element (i.e., 1 itself) which takes cost 1*7. So total cost = 9 + 7 + 3 = 16 .
Index 1: At index 1, remove all numbers after index 1. It takes cost 2 * 3 for remove and add [3 – (1 + 1)] = 1 new element which takes cost 1*7. So total cost = 6 + 7 = 13.
Index 2: At index 2, remove all numbers after index 2. It takes cost 1 * 3 for remove and add [5 – (2 + 1)] = 2 new elements which takes cost = 2* 7. So total cost = 3 + 14 = 17.
Index 3: At index 3, remove all numbers after index 3. It takes no cost. Add [6 – (3 + 1)] = 2 new elements which takes cost 2*7. So total cost = 2 + 14 = 16.
So minimum cost = 13 + 3 = 16.
Below are the steps to implement the above idea:
- Initially create a temporary array (say v[]) to store the unique elements only.
- Now sort the array v[] in ascending order.
- To remove all duplicates from the array, it takes cost X*(number of duplicates).
- Now consider the case of removing all numbers from the given array and adding number 1 which takes cost X*N + Y and consider this the answer.
- Now iterate the whole array and perform the steps mentioned above in the idea:
- In each step compare the cost with the current answer and update the answer accordingly.
- Return the minimum cost as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to find the minimum time // required to convert a given array // into a permutation int permute( int * arr, int n, int x, int y) { // Map for finding duplicate vector< int > v; map< int , int > m; for ( int i = 0; i < n; i++) { m[arr[i]]++; // Insert only a unique element in the vector if (m[arr[i]] == 1) { v.push_back(arr[i]); } } // Total duplicate in the array int duplicates = n - v.size(); int ans = 1e9 + 7; sort(v.begin(), v.end()); int n1 = v.size(); int minutes = n1 * x + y; ans = min(ans, minutes); // Iterate the whole array for ( int i = 0; i < n1; i++) { // If remove all numbers after index i, // then adding minimum numbers required // to make it permutation minutes = (n1 - i - 1) * x + (v[i] - (i + 1)) * y; ans = min(ans, minutes); } // Adding time take to remove all duplicates ans = ans + duplicates * x; return ans; } // Driver code int main() { int arr[] = { 2, 3, 6, 3, 5 }; int N = sizeof (arr) / sizeof ( int ); int X = 3, Y = 7; // Function call cout << permute(arr, N, X, Y); return 0; } |
Java
// java code to implement the above approach import java.util.*; public class GFG{ // Function to find the minimum time required to // convert a given array into a permutation static int permute( int [] arr, int n, int x, int y) { // Map for finding duplicates List<Integer> v = new ArrayList<>(); Map<Integer, Integer> m = new HashMap<>(); for ( int i = 0 ; i < n; i++) { m.put(arr[i], m.getOrDefault(arr[i], 0 ) + 1 ); // Insert only a unique element in the list if (m.get(arr[i]) == 1 ) { v.add(arr[i]); } } // Total duplicates in the array int duplicates = n - v.size(); int ans = ( int ) 1e9 + 7 ; Collections.sort(v); int n1 = v.size(); int minutes = n1 * x + y; ans = Math.min(ans, minutes); // Iterate the whole array for ( int i = 0 ; i < n1; i++) { // If remove all numbers after index i, // then adding minimum numbers required to // make it a permutation minutes = (n1 - i - 1 ) * x + (v.get(i) - (i + 1 )) * y; ans = Math.min(ans, minutes); } // Adding time taken to remove all duplicates ans += duplicates * x; return ans; } // Driver code public static void main(String[] args) { int [] arr = { 2 , 3 , 6 , 3 , 5 }; int N = arr.length; int X = 3 ; int Y = 7 ; // Function call System.out.println(permute(arr, N, X, Y)); } } |
Python3
from collections import defaultdict def permute(arr, x, y): # Dictionary to find duplicates # and list to store unique elements m = defaultdict( int ) v = [] for i in range ( len (arr)): m[arr[i]] + = 1 # Insert only a unique element in the list if m[arr[i]] = = 1 : v.append(arr[i]) # Total duplicates in the array duplicates = len (arr) - len (v) ans = float ( 'inf' ) v.sort() n1 = len (v) minutes = n1 * x + y ans = min (ans, minutes) # Iterate the whole list for i in range (n1): # If remove all numbers after index i, # then adding minimum numbers required # to make it a permutation minutes = (n1 - i - 1 ) * x + (v[i] - (i + 1 )) * y ans = min (ans, minutes) # Adding time taken to remove all duplicates ans = ans + duplicates * x return ans # Driver code arr = [ 2 , 3 , 6 , 3 , 5 ] X = 3 Y = 7 # Function call print (permute(arr, X, Y)) |
C#
// c# code to implement the above approach using System; using System.Collections.Generic; public class GFG { // Function to find the minimum time required to // convert a given array into a permutation static int Permute( int [] arr, int n, int x, int y) { // Map for finding duplicates List< int > v = new List< int >(); Dictionary< int , int > m = new Dictionary< int , int >(); for ( int i = 0; i < n; i++) { if (m.ContainsKey(arr[i])) { m[arr[i]]++; } else { m[arr[i]] = 1; v.Add(arr[i]); } } // Total duplicates in the array int duplicates = n - v.Count; int ans = ( int )1e9 + 7; v.Sort(); int n1 = v.Count; int minutes = n1 * x + y; ans = Math.Min(ans, minutes); // Iterate the whole array for ( int i = 0; i < n1; i++) { // If remove all numbers after index i, // then adding minimum numbers required to // make it a permutation minutes = (n1 - i - 1) * x + (v[i] - (i + 1)) * y; ans = Math.Min(ans, minutes); } // Adding time taken to remove all duplicates ans += duplicates * x; return ans; } // Driver code public static void Main( string [] args) { int [] arr = { 2, 3, 6, 3, 5 }; int N = arr.Length; int X = 3; int Y = 7; // Function call Console.WriteLine(Permute(arr, N, X, Y)); } } |
Javascript
// Function to find the minimum time // required to convert a given array // into a permutation const permute = (arr, n, x, y) => { // Map for finding duplicate const v = []; const m = new Map(); for (let i = 0; i < n; i++) { m.set(arr[i], (m.get(arr[i]) || 0) + 1); // Insert only a unique element in the vector if (m.get(arr[i]) === 1) { v.push(arr[i]); } } // Total duplicate in the array const duplicates = n - v.length; let ans = 1e9 + 7; v.sort((a, b) => a - b); const n1 = v.length; let minutes = n1 * x + y; ans = Math.min(ans, minutes); // Iterate the whole array for (let i = 0; i < n1; i++) { // If remove all numbers after index i, // then adding minimum numbers required // to make it permutation minutes = (n1 - i - 1) * x + (v[i] - (i + 1)) * y; ans = Math.min(ans, minutes); } // Adding time take to remove all duplicates ans = ans + duplicates * x; return ans; } // Driver code const arr = [2, 3, 6, 3, 5]; const N = arr.length; const X = 3, Y = 7; console.log(permute(arr, N, X, Y)); |
16
Time Complexity: O(N * logN)
Auxiliary Space: O(N)