Minimizing Total Cost for MEX Reduction
Given an array A[] of N integers perform the following operation till the MEX (Minimum Excluded Element) of the array is greater than 0: Pick any element of the array and remove it from the array. This operation costs MEX (A) i.e., MEX of the array A[], after removing the element. The task is to minimize Total Cost to reduce the MEX of the final array to 0.
Examples:
Input: A = [1, 0, 2, 2, 0]
Output: 2
Explanation:
- Remove 1, array becomes [0, 2, 2, 0], add MEX (a)=1 to total cost.
- Remove 0, array becomes [ 2, 2, 0], add MEX (a)=1 to total cost.
- Remove 0, array becomes [ 2, 2], add MEX (a)=0 to total cost. Now removing any element won’t increase the total cost so, minimum total score will be 2.
Input: A = [1, 2, 2, 3]
Output: 0
Explanation: As MEX of the array is already 0, removing any element won’t change the total cost.
Approach: The problem can be solved using the following approach:
The idea is to apply operations till MEX is greater than 0, because if MEX becomes 0, then total Cost won’t be changed. Till MEX(A) doesn’t become 0, we can pick any integer j, such that j<MEX(A) and delete all occurrence of j, then MEX (a) becomes j. We can apply Dynamic Programming, dp[i] represents the minimum total cost to reduce MEX of the array from i to 0.
dp[i]=min(dp[i], dp[j] + (count(j) – 1) * i + j), for all j from 0 to i-1 and count(j) is the number of occurrences of j in array a.
Follow the steps to solve the problem:
- Initialize a frequency array
freq
to count the occurrences of each element in the input arraya
. The frequency is counted only for elements less thann
. - Identify the MEX by finding the first element with a frequency of 0 in the frequency array. This MEX value is crucial for the Dynamic Programming approach.
- Initialize the dp array of size where dp[i] represents the minimum total cost to reduce MEX of the array from i to 0.
- dp[i] can be calculated by:
- Iterate j from 0 to i-1,
- dp[i]=min(dp[i], dp[j] + (count(j) – 1) * i + j)
- The base case of the recursion is when the MEX is already 0, and in such cases, the cost is 0. If the result for a specific MEX has already been calculated (
vis[mex] == 1
), it is retrieved from the memoized array (dp
) - Minimum Total Cost will be stored in dp[mex], where mex is the MEX of original array.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h> using namespace std; // Recursive function to calculate the minimum cost int memo(vector< int >& freq, vector< int >& dp, vector< int >& vis, int mex) { // Base case: if MEX is already 0, the cost is 0 if (mex == 0) return 0; // If the result for this MEX has already been // calculated, return it if (vis[mex] == 1) { return dp[mex]; } // Initialize ans with a large value int ans = 1e9; // Iterate over possible values of i less than mex for ( int i = 0; i < mex; i++) { // Calculate the cost for the current iteration ans = min(ans, (freq[i] - 1) * mex + i + memo(freq, dp, vis, i)); } // Memoize the result and mark the MEX as visited dp[mex] = ans; vis[mex] = 1; return dp[mex]; } // Function to solve the problem void solve(vector< int >& A, int n) { vector< int > freq(n, 0); // Count the frequency of elements in the array and find // MEX for ( int i = 0; i < n; i++) { cin >> A[i]; if (A[i] < n) freq[A[i]]++; } int mex = 0; // Find the MEX value for ( int i = 0; i <= n; i++) { if (freq[i] == 0) { mex = i; break ; } } vector< int > dp(mex + 1, 0); vector< int > vis(mex + 1, 0); // Call the recursive function and print the result cout << memo(freq, dp, vis, mex) << "\n" ; } // Driver Code int main() { int n = 5; vector< int > A = { 1, 0, 2, 2, 0 }; solve(A, n); } |
Java
import java.util.Arrays; import java.util.Scanner; public class Main { // Recursive function to calculate the minimum cost static int memo( int [] freq, int [] dp, int [] vis, int mex) { // Base case: if MEX is already 0, the cost is 0 if (mex == 0 ) return 0 ; // If the result for this MEX has already been // calculated, return it if (vis[mex] == 1 ) { return dp[mex]; } // Initialize ans with a large value int ans = Integer.MAX_VALUE; // Iterate over possible values of i less than mex for ( int i = 0 ; i < mex; i++) { // Calculate the cost for the current iteration ans = Math.min(ans, (freq[i] - 1 ) * mex + i + memo(freq, dp, vis, i)); } // Memoize the result and mark the MEX as visited dp[mex] = ans; vis[mex] = 1 ; return dp[mex]; } // Function to solve the problem static void solve( int [] A, int n) { int [] freq = new int [n]; // Count the frequency of elements in the array and find // MEX for ( int i = 0 ; i < n; i++) { if (A[i] < n) freq[A[i]]++; } int mex = 0 ; // Find the MEX value for ( int i = 0 ; i <= n; i++) { if (freq[i] == 0 ) { mex = i; break ; } } int [] dp = new int [mex + 1 ]; int [] vis = new int [mex + 1 ]; Arrays.fill(vis, 0 ); // Call the recursive function and print the result System.out.println(memo(freq, dp, vis, mex)); } // Driver Code public static void main(String[] args) { int n = 5 ; int [] A = { 1 , 0 , 2 , 2 , 0 }; solve(A, n); } } // This code is contributed by rambabuguphka |
Python3
# Recursive function to calculate the minimum cost def memo(freq, dp, vis, mex): # Base case: if MEX is already 0, the cost is 0 if mex = = 0 : return 0 # If the result for this MEX has already been # calculated, return it if vis[mex] = = 1 : return dp[mex] # Initialize ans with a large value ans = float ( 'inf' ) # Iterate over possible values of i less than mex for i in range (mex): # Calculate the cost for the current iteration ans = min (ans, (freq[i] - 1 ) * mex + i + memo(freq, dp, vis, i)) # Memoize the result and mark the MEX as visited dp[mex] = ans vis[mex] = 1 return dp[mex] # Function to solve the problem def solve(A, n): freq = [ 0 ] * n # Count the frequency of elements in the array and find MEX for i in range (n): if A[i] < n: freq[A[i]] + = 1 mex = 0 # Find the MEX value for i in range (n + 1 ): if freq[i] = = 0 : mex = i break dp = [ 0 ] * (mex + 1 ) vis = [ 0 ] * (mex + 1 ) # Call the recursive function and print the result print (memo(freq, dp, vis, mex)) # Driver Code if __name__ = = "__main__" : n = 5 A = [ 1 , 0 , 2 , 2 , 0 ] solve(A, n) |
C#
using System; using System.Collections.Generic; class Program { // Recursive function to calculate the minimum cost static int Memo(List< int > freq, List< int > dp, List< int > vis, int mex) { // Base case: if MEX is already 0, the cost is 0 if (mex == 0) return 0; // If the result for this MEX has already been // calculated, return it if (vis[mex] == 1) { return dp[mex]; } // Initialize ans with a large value int ans = int .MaxValue; // Iterate over possible values of i less than mex for ( int i = 0; i < mex; i++) { // Calculate the cost for the current iteration ans = Math.Min(ans, (freq[i] - 1) * mex + i + Memo(freq, dp, vis, i)); } // Memoize the result and mark the MEX as visited dp[mex] = ans; vis[mex] = 1; return dp[mex]; } // Function to solve the problem static void Solve(List< int > A, int n) { List< int > freq = new List< int >( new int [n]); // Count the frequency of elements in the array and find MEX for ( int i = 0; i < n; i++) { if (A[i] < n) freq[A[i]]++; } int mex = 0; // Find the MEX value for ( int i = 0; i <= n; i++) { if (freq[i] == 0) { mex = i; break ; } } List< int > dp = new List< int >( new int [mex + 1]); List< int > vis = new List< int >( new int [mex + 1]); // Call the recursive function and print the result Console.WriteLine(Memo(freq, dp, vis, mex)); } // Driver Code static void Main() { int n = 5; List< int > A = new List< int > { 1, 0, 2, 2, 0 }; Solve(A, n); } } |
Javascript
// Recursive function to calculate the minimum cost function memo(freq, dp, vis, mex) { // Base case: if MEX is already 0, the cost is 0 if (mex === 0) return 0; // If the result for this MEX has already been // calculated, return it if (vis[mex] === 1) { return dp[mex]; } // Initialize ans with a large value let ans = 1e9; // Iterate over possible values of i less than mex for (let i = 0; i < mex; i++) { // Calculate the cost for the current iteration ans = Math.min(ans, (freq[i] - 1) * mex + i + memo(freq, dp, vis, i)); } // Memoize the result and mark the MEX as visited dp[mex] = ans; vis[mex] = 1; return dp[mex]; } // Function to solve the problem function solve(A, n) { let freq = new Array(n).fill(0); // Count the frequency of elements in the array and find MEX for (let i = 0; i < n; i++) { if (A[i] < n) freq[A[i]]++; } let mex = 0; // Find the MEX value for (let i = 0; i <= n; i++) { if (freq[i] === 0) { mex = i; break ; } } let dp = new Array(mex + 1).fill(0); let vis = new Array(mex + 1).fill(0); // Call the recursive function and print the result console.log(memo(freq, dp, vis, mex)); } // Driver Code function main() { let n = 5; let A = [1, 0, 2, 2, 0]; solve(A, n); } // Calling the main function main(); |
2
Time Complexity: O(N2), where N is the number of elements in the input array A[].
Auxiliary Space: O(N)
Contact Us