Maximize MEX by adding or subtracting K from Array elements

0 0 5 minutes read

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 subtraction
int 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 code
int 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 approach
from collections import defaultdict
 
# Function to find maximum MEX of the array
# after doing some addition and subtraction
def 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 code
if __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 subtraction
function 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

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 zambiatek!