# MEX Number ## Solution 1: Direct MEX Computation with Frequency Counting ### Intuition - The MEX is the smallest non-negative integer missing from the array. - To change the MEX, we can either increase it or decrease it. - Decreasing the MEX requires adding a missing number, which is not an option since we can only remove elements. - Increasing the MEX requires removing all occurrences of a number from `0` to `current_MEX - 1`. - If we remove all occurrences of the MEX itself, the MEX stays the same, so we cannot remove the MEX. - The only valid way is to remove all occurrences of some number smaller than the current MEX. ### Approach - Compute the MEX of the original array by counting frequencies. - If the MEX is zero, all elements are already non-zero; removing any element keeps MEX as zero, so return `-2`. - For a non-zero MEX, check each number from `0` to `MEX - 1` and count how many times it appears. - The minimum count among these numbers is the minimum elements to remove. - If any number from `0` to `MEX - 1` is already missing, MEX would be smaller, but our computed MEX assumes this isn't the case. ### Pseudocode ``` function findMinRemovals(array, n) { maxElement = maximum value in array frequency = array of size (maxElement + 2) initialized to 0 for each element in array { frequency[element] = frequency[element] + 1 } mex = 0 while mex <= maxElement and frequency[mex] > 0 { mex = mex + 1 } if mex == 0 { return -2 } minRemovals = infinity for i = 0 to mex - 1 { if frequency[i] < minRemovals { minRemovals = frequency[i] } } return minRemovals } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int findMinRemovals(vector& arr, int n) { int maxElement = 0; for (int i = 0; i < n; i++) { if (arr[i] > maxElement) { maxElement = arr[i]; } } vector frequency(maxElement + 2, 0); for (int i = 0; i < n; i++) { frequency[arr[i]]++; } int mex = 0; while (mex <= maxElement && frequency[mex] > 0) { mex++; } if (mex == 0) { return -2; } int minRemovals = INT_MAX; for (int i = 0; i < mex; i++) { if (frequency[i] < minRemovals) { minRemovals = frequency[i]; } } return minRemovals; } }; /* int main() { int n; cin >> n; vector arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } solution sol; cout << sol.findMinRemovals(arr, n); return 0; } */ ``` **Python** ```python class solution: def findMinRemovals(self, arr, n): if n == 0: return -2 maxElement = max(arr) frequency = {} for num in arr: frequency[num] = frequency.get(num, 0) + 1 mex = 0 while mex <= maxElement and mex in frequency: mex += 1 if mex == 0: return -2 minRemovals = float('inf') for i in range(mex): if i in frequency and frequency[i] < minRemovals: minRemovals = frequency[i] elif i not in frequency: minRemovals = 0 return minRemovals if minRemovals != float('inf') else 0 ''' n = int(input()) arr = list(map(int, input().split())) sol = solution() print(sol.findMinRemovals(arr, n)) ''' ``` **Java** ```java import java.util.*; class Solution { public static int findMinRemovals(int[] arr, int n) { int maxElement = 0; for (int i = 0; i < n; i++) { if (arr[i] > maxElement) { maxElement = arr[i]; } } int[] frequency = new int[maxElement + 2]; for (int i = 0; i < n; i++) { frequency[arr[i]]++; } int mex = 0; while (mex <= maxElement && frequency[mex] > 0) { mex++; } if (mex == 0) { return -2; } int minRemovals = Integer.MAX_VALUE; for (int i = 0; i < mex; i++) { if (frequency[i] < minRemovals) { minRemovals = frequency[i]; } } return minRemovals; } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } System.out.println(Solution.findMinRemovals(arr, n)); } } */ ``` **JavaScript** ```javascript class Solution { static findMinRemovals(arr, n) { let maxElement = 0; for (let i = 0; i < n; i++) { if (arr[i] > maxElement) { maxElement = arr[i]; } } let frequency = new Array(maxElement + 2).fill(0); for (let i = 0; i < n; i++) { frequency[arr[i]]++; } let mex = 0; while (mex <= maxElement && frequency[mex] > 0) { mex++; } if (mex === 0) { return -2; } let minRemovals = Infinity; for (let i = 0; i < mex; i++) { if (frequency[i] < minRemovals) { minRemovals = frequency[i]; } } return minRemovals; } } /* function main() { const fs = require("fs"); const data = fs.readFileSync(0, "utf8").trim().split(/\s+/); let idx = 0; const n = Number(data[idx++]); const arr = new Array(n); for (let i = 0; i < n; i++) { arr[i] = Number(data[idx++]); } console.log(Solution.findMinRemovals(arr, n)); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(n + maxElement)` — Finding the maximum takes `O(n)`, building frequency takes `O(n)`, finding MEX takes `O(maxElement)` (maxElement ≤ 90). - **Space Complexity:** `O(maxElement)` — The frequency array has size `maxElement + 2`. --- ## Solution 2: Hash Set MEX with Minimum Frequency Lookup ### Intuition - Using a hash set provides O(1) lookups for checking if a number exists. - First, determine the MEX using a set by checking consecutive integers starting from 0. - If MEX is positive, we need to remove all occurrences of any number from 0 to MEX-1. - A frequency map helps track how many times each number appears. - The answer is the minimum frequency among all numbers from 0 to MEX-1. ### Approach - Store all array elements in a hash set and also maintain a frequency map. - Iterate from 0 onwards to find the smallest missing number (MEX). - If MEX is 0, return `-2` since we cannot make MEX smaller. - For each number from 0 to MEX-1, check its frequency in the map. - Return the smallest frequency as it represents the minimum deletions needed. ### Pseudocode ``` function findMinRemovals(array, n) { numberSet = empty hash set frequencyMap = empty hash map for each element in array { add element to numberSet frequencyMap[element] = frequencyMap.get(element, 0) + 1 } mex = 0 while numberSet contains mex { mex = mex + 1 } if mex == 0 { return -2 } minRemovals = infinity for i = 0 to mex - 1 { count = frequencyMap.get(i, 0) if count < minRemovals { minRemovals = count } } return minRemovals } ``` ### Code Implementation **C++** ```cpp #include using namespace std; class solution { public: int findMinRemovals(vector& arr, int n) { unordered_set numberSet; unordered_map frequencyMap; for (int i = 0; i < n; i++) { numberSet.insert(arr[i]); frequencyMap[arr[i]]++; } int mex = 0; while (numberSet.find(mex) != numberSet.end()) { mex++; } if (mex == 0) { return -2; } int minRemovals = INT_MAX; for (int i = 0; i < mex; i++) { int count = frequencyMap[i]; if (count < minRemovals) { minRemovals = count; } } return minRemovals; } }; /* int main() { int n; cin >> n; vector arr(n); for (int i = 0; i < n; i++) { cin >> arr[i]; } solution sol; cout << sol.findMinRemovals(arr, n); return 0; } */ ``` **Python** ```python class solution: def findMinRemovals(self, arr, n): numberSet = set() frequencyMap = {} for num in arr: numberSet.add(num) frequencyMap[num] = frequencyMap.get(num, 0) + 1 mex = 0 while mex in numberSet: mex += 1 if mex == 0: return -2 minRemovals = float('inf') for i in range(mex): count = frequencyMap.get(i, 0) if count < minRemovals: minRemovals = count return minRemovals ''' n = int(input()) arr = list(map(int, input().split())) sol = solution() print(sol.findMinRemovals(arr, n)) ''' ``` **Java** ```java import java.util.*; class Solution { public static int findMinRemovals(int[] arr, int n) { HashSet numberSet = new HashSet<>(); HashMap frequencyMap = new HashMap<>(); for (int i = 0; i < n; i++) { numberSet.add(arr[i]); frequencyMap.put(arr[i], frequencyMap.getOrDefault(arr[i], 0) + 1); } int mex = 0; while (numberSet.contains(mex)) { mex++; } if (mex == 0) { return -2; } int minRemovals = Integer.MAX_VALUE; for (int i = 0; i < mex; i++) { int count = frequencyMap.getOrDefault(i, 0); if (count < minRemovals) { minRemovals = count; } } return minRemovals; } } /* public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] arr = new int(n); for (int i = 0; i < n; i++) { arr[i] = scanner.nextInt(); } System.out.println(Solution.findMinRemovals(arr, n)); } } */ ``` **JavaScript** ```javascript class Solution { static findMinRemovals(arr, n) { let numberSet = new Set(); let frequencyMap = new Map(); for (let i = 0; i < n; i++) { numberSet.add(arr[i]); frequencyMap.set(arr[i], (frequencyMap.get(arr[i]) || 0) + 1); } let mex = 0; while (numberSet.has(mex)) { mex++; } if (mex === 0) { return -2; } let minRemovals = Infinity; for (let i = 0; i < mex; i++) { let count = frequencyMap.get(i) || 0; if (count < minRemovals) { minRemovals = count; } } return minRemovals; } } /* function main() { const fs = require("fs"); const data = fs.readFileSync(0, "utf8").trim().split(/\s+/); let idx = 0; const n = Number(data[idx++]); const arr = new Array(n); for (let i = 0; i < n; i++) { arr[i] = Number(data[idx++]); } console.log(Solution.findMinRemovals(arr, n)); } main(); */ ``` ### Complexity Analysis - **Time Complexity:** `O(n + mex)` — Building the hash set and frequency map takes `O(n)`, finding MEX takes `O(mex)` (mex ≤ n+1). - **Space Complexity:** `O(n)` — The hash set and frequency map store at most `n` distinct elements.