Minimize the sum of MEX by removing all elements of array
Given an array of integers arr[] of size N. You can perform the following operation N times: Pick any index i, and remove arr[i] from the array and add MEX(arr[]) i.e., Minimum Excluded of the array arr[] to your total score. Your task is to minimize the total score.
Examples:
Input: N = 8, arr[] = {5, 2, 1, 0, 3, 0, 4, 0}
Output: 3
Explanation: We remove elements from arr[] in the following order:
- Remove arr[2] = 1, so arr[] becomes {5, 2, 0, 3, 0, 4, 0} and MEX(arr[]) = 1
- Remove arr[2] = 0, so arr[] becomes {5, 2, 3, 0, 4, 0} and MEX(arr[]) = 1
- Remove arr[3] = 0, so arr[] becomes {5, 2, 3, 4, 0} and MEX(arr[]) = 1
- Remove arr[4] = 0, so arr[] becomes {5, 2, 3, 4} and MEX(arr[]) = 0
- Remove arr[0] = 5, so arr[] becomes {2, 3, 4} and MEX(arr[]) = 0
- Remove arr[0] = 2, so arr[] becomes {3, 4} and MEX(arr[]) = 0
- Remove arr[0] = 3, so arr[] becomes {4} and MEX(arr[]) = 0
- Remove arr[0] = 4, so arr[] becomes {} and MEX(arr[]) = 0
Total score = 1 + 1 + 1 + 0 + 0 + 0 + 0 + 0 = 3
Input: N = 8, arr[] = {0, 1, 2, 0, 1, 2, 0, 3}
Output: 7
Explanation: We remove elements from arr[] in the following order:
- Remove arr[1] = 1, so arr[] becomes {0, 2, 0, 1, 2, 0, 3} and MEX(arr[]) = 4
- Remove arr[3] = 1, so arr[] becomes {0, 2, 0, 2, 0, 3} and MEX(arr[]) = 1
- Remove arr[0] = 0, so arr[] becomes {2, 0, 2, 0, 3} and MEX(arr[]) = 1
- Remove arr[1] = 0, so arr[] becomes {2, 2, 0, 3} and MEX(arr[]) = 1
- Remove arr[2] = 0, so arr[] becomes {2, 2, 3} and MEX(arr[]) = 0
- Remove arr[0] = 2, so arr[] becomes {2, 3} and MEX(arr[]) = 0
- Remove arr[0] = 2, so arr[] becomes {3} and MEX(arr[]) = 0
- Remove arr[0] = 3, so arr[] becomes {} and MEX(arr[]) = 0
Total score = 4 + 1 + 1 + 1 + 0 + 0 + 0 + 0 = 7
Approach: To solve the problem, follow the below idea:
We know that the total score will increase only till MEX(arr[]) is not equal to 0. Once MEX(arr[]) becomes 0, the total score will not change.
Since, we need to minimize the total sum of MEX after all deletions, we will first remove elements from the array which are smaller than the MEX(arr[]) because if we remove the elements which are greater than MEX(arr[]) then our MEX(arr[]) will not reduce. We can always delete the elements which are greater than MEX(arr[]) after the MEX has reached 0.
Now, we will use Dynamic Programming to calculate the minimum score such that dp[i] stores the minimum score to make MEX(arr[]) = i.
Maintain a frequency map freq such that freq[x] stores the frequency of x in arr[]. So, the transition will be:For all (j < i), dp[j] = min(dp[j], dp[i] + (freq[j] – 1) * i + j)
Step-by-step algorithm:
- Maintain a map freq to store the frequency of each element in arr[].
- Find the MEX of arr[] and store it in currentMEX.
- Maintain a dp[] array such that dp[i] stores the minimum score to make MEX(arr[]) = i.
- Iterate i from currentMEX to 1:
- Iterate j from 0 to i – 1 and update dp[j] = min(dp[j], dp[i] + i * (freq[j] – 1) + j)
- Finally, return dp[0] as the final answer.
Below is the implementation of the algorithm:
#include <iostream>
#include <vector>
#include <map>
using namespace std;
#define int long long
void solve()
{
int N = 8, currentMEX = 0;
// Define a map to store frequencies of elements
map<int, int> freq;
// Define input array
int arr[] = {0, 1, 2, 0, 1, 2, 0, 3};
for (int i = 0; i < N; i++) {
// Count the frequencies of elements
freq[arr[i]]++;
}
// Find the maximum element
while (freq[currentMEX] > 0) {
currentMEX++;
}
// Initialize a vector with large values
vector<int> dp(currentMEX + 1, 1e9);
// Initialize the last element of dp to 0
dp[currentMEX] = 0;
// Dynamic Programming approach
for (int i = currentMEX; i > 0; i--) {
for (int j = 0; j < i; j++) {
// Update the dp array
dp[j] = min(dp[j], dp[i] + i * (freq[j] - 1) + j);
}
}
// Output the result
cout << dp[0] << endl;
}
signed main()
{
// Call the solve function
solve();
return 0;
}
import java.util.*;
public class Main {
public static void solve() {
int N = 8, currentMEX = 0;
// Define a map to store frequencies of elements
Map<Integer, Integer> freq = new HashMap<>();
// Define input array
int[] arr = {0, 1, 2, 0, 1, 2, 0, 3};
for (int i = 0; i < N; i++) {
// Count the frequencies of elements
freq.put(arr[i], freq.getOrDefault(arr[i], 0) + 1);
}
// Find the maximum element
while (freq.containsKey(currentMEX)) {
currentMEX++;
}
// Initialize an array with large values
int[] dp = new int[currentMEX + 1];
Arrays.fill(dp, (int)1e9);
// Initialize the last element of dp to 0
dp[currentMEX] = 0;
// Dynamic Programming approach
for (int i = currentMEX; i > 0; i--) {
for (int j = 0; j < i; j++) {
// Update the dp array
dp[j] = Math.min(dp[j], dp[i] + i * (freq.getOrDefault(j, 0) - 1) + j);
}
}
// Output the result
System.out.println(dp[0]);
}
public static void main(String[] args) {
// Call the solve function
solve();
}
}
def solve():
N = 8
currentMEX = 0
# Define a dictionary to store frequencies of elements
freq = {}
# Define input array
arr = [0, 1, 2, 0, 1, 2, 0, 3]
# Count the frequencies of elements
for i in range(N):
freq[arr[i]] = freq.get(arr[i], 0) + 1
# Find the maximum element
while currentMEX in freq:
currentMEX += 1
# Initialize a list with large values
dp = [10**9] * (currentMEX + 1)
# Initialize the last element of dp to 0
dp[currentMEX] = 0
# Dynamic Programming approach
for i in range(currentMEX, 0, -1):
for j in range(i):
# Update the dp list
dp[j] = min(dp[j], dp[i] + i * (freq.get(j, 0) - 1) + j)
# Output the result
print(dp[0])
# Call the solve function
solve()
function solve() {
const N = 8;
let currentMEX = 0;
// Define a map to store frequencies of elements
const freq = {};
// Define input array
const arr = [0, 1, 2, 0, 1, 2, 0, 3];
// Count the frequencies of elements
for (let i = 0; i < N; i++) {
freq[arr[i]] = (freq[arr[i]] || 0) + 1;
}
// Find the maximum element
while (freq[currentMEX]) {
currentMEX++;
}
// Initialize an array with large values
const dp = Array(currentMEX + 1).fill(10**9);
// Initialize the last element of dp to 0
dp[currentMEX] = 0;
// Dynamic Programming approach
for (let i = currentMEX; i > 0; i--) {
for (let j = 0; j < i; j++) {
// Update the dp array
dp[j] = Math.min(dp[j], dp[i] + i * ((freq[j] || 0) - 1) + j);
}
}
// Output the result
console.log(dp[0]);
}
// Call the solve function
solve();
Output
7
Time complexity: O(N * N), where N is the size of input array arr[]
Auxiliary Space: O(N)