Given an array ‘arr’ consisting of N arrays, each of size M, the task is to find the minimum number of operations required to make the Minimum Excluded Element (MEX) the same for all N arrays. You can perform the following task zero or more times:
- Choose one of the N arrays.
- Choose some non-negative integer ‘x’ and append it to the chosen array.
Examples:
Input: arr = { {2, 2, 3}, {4, 1, 3}, {3, 1, 2} }
Output: 4
Explanation: 1, 2, 3, 4 can not be the MEX as none of all four is a number that is not present in all the 3 arrays, but 5 is not present in all three so to make 5 as MEX of all three we have to add 1, 4 in the first array and 2 in second and 4 in third after this arrays will look like {2, 2, 3, 1, 4}, {4, 1, 3, 2},
{3, 1, 2, 4}, and their MEX will be 5.Input: arr = { {1, 2, 2}, {1, 1, 1}, {2, 1, 2} }
Output: 1
Explanation: 3 is the smallest positive number that is not present in all three arrays. So to make 3 as MEX we have to add 2 in the second array and that will take a total of 1 operation.
Approach: To solve the problem follow the below observations:
Observations:
- As we have to find the smallest missing number from all arrays, So we will start with the smallest positive number 1.
- If one is present in at least one of the arrays then this number can not be a number that is missing from all arrays so we have to do operations to add 1 in arrays in which it is not present.
- For step-2 total operation will be the total number of arrays in which 1 is not present.
- Then we will go to the next element which is 2 and do the same operation until we get an element that is not present in the array.
- While doing step-2 to step-4, we will keep updating our number of operations as said in step-3.
- In last, we will return the total number of operations.
Follow the steps to solve the problem:
- First, we will take an ans variable to store the number of operations
- After this, we will take a HashMap for each N array and store the elements present in each array so that we can get the information on whether an element is present in this array or not in O(1) time.
- After this, we will take the number variable which will represent the minimum positive number that is not present in all arrays.
- After this, we have to traverse all arrays until we get an element that is not present in all arrays.
- While traversing we will keep track of the total variable that number is not present in how many arrays.
- If that number is not present in all arrays then the total will be equal to N else it will not.
- If not present in all arrays then we have to return our ans variable
- Else we have to add the number of operations to add this number in which arrays this number is not present.
Below is the implementation for the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;int MexEquality(int N, int M, vector<vector<int> >& Arr){ // Variable to store minimum number // of operations int ans = 0; // To store which element is present or not unordered_map<int, int> mm[N]; // Storing which element is present for (int i = 0; i < N; i++) { for (auto x : Arr[i]) { mm[i][x] = 1; } } // To start with minimum positive number as // explained in explanation int number = 1; // Until we got our answer while (true) { // i for iteration and // total, for arrays which do not // contain number int i, total = 0; for (i = 0; i < N; i++) { if (mm[i][number] == 0) { total++; } } // If all arrays do not contain number if (total == N) return ans; // Else add that element in all those // array and increase operations ans += total; number++; } return ans;}// Drivers codeint main(){ int N, M; vector<vector<int> > Arr{ { 1, 2, 2 }, { 1, 1, 1 }, { 2, 1, 2 } }; N = Arr.size(); M = Arr[0].size(); // Functional call cout << MexEquality(N, M, Arr); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;public class GFG { static int MexEquality(int N, int M, List<List<Integer>> Arr) { // Variable to store the minimum number of operations int ans = 0; // To store which element is present or not HashMap<Integer, Integer>[] mm = new HashMap[N]; for (int i = 0; i < N; i++) { mm[i] = new HashMap<>(); for (int x : Arr.get(i)) { mm[i].put(x, 1); } } // To start with the minimum positive number as explained in the explanation int number = 1; // Until we get our answer while (true) { // 'i' for iteration and 'total' for arrays which do not contain the number int i, total = 0; for (i = 0; i < N; i++) { if (!mm[i].containsKey(number)) { total++; } } // If all arrays do not contain the number if (total == N) return ans; // Else add that element in all those arrays and increase operations ans += total; number++; } } public static void main(String[] args) { int N, M; List<List<Integer>> Arr = new ArrayList<>(); Arr.add(Arrays.asList(1, 2, 2)); Arr.add(Arrays.asList(1, 1, 1)); Arr.add(Arrays.asList(2, 1, 2)); N = Arr.size(); M = Arr.get(0).size(); // Functional call System.out.println(MexEquality(N, M, Arr)); }} |
Python3
# Function to calculate the minimum number of operationsdef MexEquality(N, M, Arr): ans = 0 mm = [{} for _ in range(N)] # Create a list of dictionaries for each row # Fill in the dictionaries with elements from the matrix for i in range(N): for x in Arr[i]: mm[i][x] = 1 number = 1 # Start with the minimum positive number while True: i, total = 0, 0 # Count the number of arrays that do not contain the current number for i in range(N): if mm[i].get(number, 0) == 0: total += 1 # If all arrays do not contain the current number, return the answer if total == N: return ans ans += total # Add the count of arrays that don't contain the number to the answer number += 1 # Move to the next number return ans# Driver codeif __name__ == "__main__": Arr = [[1, 2, 2], [1, 1, 1], [2, 1, 2]] N = len(Arr) # Number of rows M = len(Arr[0]) # Number of columns # Function call and output the result print(MexEquality(N, M, Arr))#This code is contributed by chinmaya121221 |
C#
using System;using System.Collections.Generic;class Program{ static int MexEquality(int N, int M, List<List<int>> Arr) { // Variable to store minimum number // of operations int ans = 0; // To store which element is present or not Dictionary<int, int>[] mm = new Dictionary<int, int>[N]; // Storing which element is present for (int i = 0; i < N; i++) { mm[i] = new Dictionary<int, int>(); foreach (int x in Arr[i]) { mm[i][x] = 1; } } // To start with minimum positive number as // explained in explanation int number = 1; // Until we got our answer while (true) { // i for iteration and // total, for arrays which do not // contain number int total = 0; for (int i = 0; i < N; i++) { if (!mm[i].ContainsKey(number)) { total++; } } // If all arrays do not contain number if (total == N) { return ans; } // Else add that element in all those // array and increase operations ans += total; number++; } //return ans; } // Drivers code static void Main(string[] args) { int N, M; List<List<int>> Arr = new List<List<int>>() { new List<int>() { 1, 2, 2 }, new List<int>() { 1, 1, 1 }, new List<int>() { 2, 1, 2 } }; N = Arr.Count; M = Arr[0].Count; Console.WriteLine(MexEquality(N, M, Arr)); }} |
Javascript
function MexEquality(N, M, Arr) { // Variable to store the minimum number of operations let ans = 0; let mm = new Array(N); for (let i = 0; i < N; i++) { // To store which element is present or not mm[i] = new Map(); for (let x of Arr[i]) { mm[i].set(x, 1); } } // To start with the minimum positive number as explained in the explanation let number = 1; // Until we get our answer while (true) { // 'i' for iteration and 'total' for arrays which do not contain the number let total = 0; for (let i = 0; i < N; i++) { if (!mm[i].has(number)) { total++; } } // If all arrays do not contain the number if (total === N) { return ans; } // Else add that element in all those arrays and increase operations ans += total; number++; }}let N, M;let Arr = [];Arr.push([1, 2, 2]);Arr.push([1, 1, 1]);Arr.push([2, 1, 2]);N = Arr.length;M = Arr[0].length;// Functional callconsole.log(MexEquality(N, M, Arr)); |
Output
1
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
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!
Share your thoughts in the comments
