Given an arr[] of size N and an integer, K, the task is to find the maximum possible value of MEX by adding or subtracting K any number of times from the array elements.
MEX is the minimum non-negative integer that is not present in the array
Examples:
Input: arr[]={1, 3, 4}, K = 2
Output: 2
Explanation: After subtracting K from arr[2] twice,
the final array will be {1, 3, 0}.
So the MEX is 2 which is maximum possible answer.Input: arr[] = {0, 1, 2, 1, 3}, K = 3
Output: 5
Explanation: After adding K to arr[1], the final array will be {0, 4, 2, 1, 3}.
So the MEX is 5 which is maximum possible answer.
Approach: Follow the below idea to solve the problem:
The maximum MEX which can be achieved from an array of size N is N. For this, we need to have all the elements from 0 to N – 1 by doing some operations. If there is a number that is not achievable by doing some operation then this is the answer.
We can generate a number x from a number p by doing addition or subtraction if both remainders are same by diving it with K [i.e., the difference between them is divisible by K].
Follow the steps to solve the problem:
- Create a map that stores the frequency of the remainder of all the elements of the array.
- Traverse from 0 to N-1 and check if there is a need to generate the number x then x % K must be present in the map.
- If it is present in the map then decrease the frequency of x % K and continue.
- Else, return the number as the answer.
Below is the implementation for the above approach:
C++
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;// Function to find maximum MEX of the array// after doing some addition and subtractionint mex(int arr[], int n, int K){ // Create a map to store the frequency of // remainder of all element by K unordered_map<int, int> mp; for (int i = 0; i < n; i++) { mp[arr[i] % K]++; } for (int i = 0; i < n; i++) { // In order to generate i find an // element whose modulo value is equal // to i%K, return i as answer if no // such value is found if (mp.find(i % K) == mp.end()) { return i; } // If we find element whose modulo // value equal to i%K mp[i % K]--; if (mp[i % K] == 0) mp.erase(i % K); } return n;}// Driver codeint main(){ int arr[] = { 0, 1, 2, 1, 3 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 3; // Function call cout << mex(arr, N, K) << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.*;import java.util.HashMap;class GFG { // Function to find maximum MEX of the array // after doing some addition and subtraction public static int mex(int[] arr, int n, int K) { Map<Integer, Integer> mp = new HashMap<Integer, Integer>(); for (int v : arr) { mp.putIfAbsent(v % K, 0); mp.put(v % K, mp.get(v % K) + 1); } for (int i = 0; i < n; i++) { if (!mp.containsKey(i % K)) { return i; } mp.put(i % K, mp.get(i % K) - 1); if (mp.get(i % K) <= 0) { mp.remove(i % K); } } return n; } public static void main(String[] args) { int arr[] = { 0, 1, 2, 1, 3 }; int N = arr.length; int K = 3; // Function call System.out.println(mex(arr, N, K)); }}// This code is contributed by akashish__ |
Python3
# Python code to implement the approachfrom collections import defaultdict# Function to find maximum MEX of the array# after doing some addition and subtractiondef mex(arr, n, K) : # Create a map to store the frequency of # remainder of all element by K mp = defaultdict(lambda : 0) # Traverse the array for i in range(n): # Update frequency of arr[i] mp[arr[i] % K] += 1; for i in range(n): # In order to generate i find an # element whose modulo value is equal # to i%K, return i as answer if no # such value is found if ((i % K) not in mp) : return i # If we find element whose modulo # value equal to i%K mp[i % K] -= 1 if (mp[i % K] == 0) : del mp[i % K] return n# Driver codeif __name__ == "__main__": arr = [ 0, 1, 2, 1, 3 ] N = len(arr) K = 3 # Function call print(mex(arr, N, K)) # This code is contributed by sanjoy_62. |
C#
/*package whatever //do not write package name here */using System;using System.Collections.Generic;public class GFG { // Function to find maximum MEX of the array // after doing some addition and subtraction public static int mex(int[] arr, int n, int K) { // Create a map to store the frequency of // remainder of all element by K Dictionary<int, int> mp = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { mp.Add(i, 0); } for (int i = 0; i < n; i++) { if(mp.ContainsKey(arr[i] % K)) mp[mp[arr[i] % K]]= mp[arr[i] % K] + 1; else mp.Add(mp[arr[i] % K], 1); } for (int i = 0; i < n; i++) { // In order to generate i find an // element whose modulo value is equal // to i%K, return i as answer if no // such value is found if (mp[i%K] > 1 ){ return i; } // If we find element whose modulo // value equal to i%K if(mp.ContainsKey(arr[i] % K)) mp[mp[arr[i] % K]]= mp[arr[i] % K] - 1; if (mp.ContainsKey(i % K) && mp[i % K] <= 0) mp[mp[arr[i] % K]]= 0; } return n; } public static void Main(String[] args) { int []arr = { 0, 1, 2, 1, 3 }; int N = arr.Length; int K = 3; // Function call Console.WriteLine(mex(arr, N, K)); }}// This code contributed by shikhasingrajput |
Javascript
<script>// Javascript code for the above approach// Function to find maximum MEX of the array// after doing some addition and subtractionfunction mex(arr,n,K){ // Create a map to store the frequency of // remainder of all element by K let mp=new Map(); for (let i = 0; i < n; i++) { mp[arr[i] % K]++; } for (let i = 0; i < n; i++) { // In order to generate i find an // element whose modulo value is equal // to i%K, return i as answer if no // such value is found if (mp.has(i % K)) { return i; } // If we find element whose modulo // value equal to i%K mp[i % K]--; if (mp[i % K] == 0) mp.delete(i % K); } return n;}// Driver code let arr = [ 0, 1, 2, 1, 3 ]; let N = arr.length; let K = 3; // Function call document.write(mex(arr, N, K)); // This code is contributed by satwik4409. </script> |
Output
5
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
