Horje
Find minimum length for Maximum Mex Subsequence

Given an array A[] consisting of N integers. You have to choose a subsequence from the given array such that the mex of that chosen subsequence is maximum. The task is to return the minimum length of such subsequence.

Examples:

Input: N = 7, A[] = {1, 2, 1, 2, 1, 4, 0}
Output: 3
Explanation: We can choose {1, 2, 0} having mex 3 which is the maximum possible.

Input: N = 3, A[] = {1, 1, 2}
Output: 0
Explanation: The maximum mex we can get is 0 which is of empty sub-sequence.

Approach: This can be solved with the following idea:

Using Map data structure, we can start iterating from number 0. If present in array, iterate to next number, otherwise break and return the number.

Below are the steps involved:

  • Initialise a map m.
  • Add elements of an array into map m.
  • Start iterating from i = 0.
    • If i is present, iterate further by incrementing 1.
    • If not, break and return i.

Below is the implementation of the code:

C++

// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
 
// Function to find minimum length
// subsequence with maximum mex
int solve(int N, vector<int>& A)
{
    // Intialize a map
    unordered_map<int, int> m;
 
    int i = 0;
 
    // Add it into a map
    while (i < A.size()) {
 
        m[A[i]]++;
        i = i + 1;
    }
 
    // Start iterating from 0
    i = 0;
    while (true) {
 
        // If not present
        if (m.find(i) == m.end()) {
            return i;
        }
        i = i + 1;
    }
 
    return -1;
}
 
// Driver code
int main()
{
 
    int N = 5;
    vector<int> A = { 0, 1, 3, 4, 2 };
 
    // Function call
    cout << solve(N, A);
    return 0;
}

Java

// Java code to implement the above approach
 
import java.util.*;
 
public class GFG {
    // Function to find minimum length
    // subsequence with maximum mex
    static int solve(int N, Vector<Integer> A)
    {
        // Intialize a map
        Map<Integer, Integer> m = new HashMap<>();
 
        int i = 0;
 
        // Add it into a map
        while (i < A.size()) {
            m.put(A.get(i),
                  m.getOrDefault(A.get(i), 0) + 1);
            i = i + 1;
        }
 
        // Start iterating from 0
        i = 0;
        while (true) {
 
            // If not present
            if (!m.containsKey(i)) {
                return i;
            }
            i = i + 1;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int N = 5;
        Vector<Integer> A = new Vector<>();
        A.add(0);
        A.add(1);
        A.add(3);
        A.add(4);
        A.add(2);
 
        // Function call
        System.out.println(solve(N, A));
    }
}
 
// This code is contributed by Abhinav Mahajan (abhinav_m22)

Python3

# Function to find minimum length subsequence with maximum mex
def solve(N, A):
    # Initialize a dictionary
    m = {}
     
    i = 0
 
    # Add elements to the dictionary
    while i < len(A):
        if A[i] in m:
            m[A[i]] += 1
        else:
            m[A[i]] = 1
        i += 1
 
    # Start iterating from 0
    i = 0
    while True:
        # If not present in the dictionary
        if i not in m:
            return i
        i += 1
 
    # Return -1 if not found (this line is not reachable)
    return -1
 
# Driver code
if __name__ == "__main__":
    N = 5
    A = [0, 1, 3, 4, 2]
 
    # Function call
    print(solve(N, A))

C#

using System;
using System.Collections.Generic;
 
public class GFG {
    // Function to find minimum length
    // subsequence with maximum mex
    static int Solve(int N, List<int> A)
    {
        // Intialize a dictionary
        Dictionary<int, int> m = new Dictionary<int, int>();
 
        int i = 0;
 
        // Add it into a dictionary
        while (i < A.Count) {
            if (m.ContainsKey(A[i]))
                m[A[i]]++;
            else
                m[A[i]] = 1;
            i = i + 1;
        }
 
        // Start iterating from 0
        i = 0;
        while (true) {
            // If not present
            if (!m.ContainsKey(i)) {
                return i;
            }
            i = i + 1;
        }
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int N = 5;
        List<int> A = new List<int>{ 0, 1, 3, 4, 2 };
 
        // Function call
        Console.WriteLine(Solve(N, A));
    }
}

Javascript

function solve(N, A) {
    // Initialize a Map to store the frequency of elements
    const m = new Map();
 
    let i = 0;
 
    // Add elements to the Map
    while (i < A.length) {
        if (m.has(A[i])) {
            m.set(A[i], m.get(A[i]) + 1);
        } else {
            m.set(A[i], 1);
        }
        i++;
    }
 
    // Start iterating from 0
    i = 0;
    while (true) {
        // If 'i' is not present in the Map, it is the minimum element not in the array
        if (!m.has(i)) {
            return i;
        }
        i++;
    }
 
    return -1;
}
 
// Driver code
const N = 5;
const A = [0, 1, 3, 4, 2];
 
// Function call
console.log(solve(N, A));

Output

5

Time Complexity: O(N)
Auxiliary Space: O(N)


 


Reffered: https://www.geeksforgeeks.org

Arrays

Related
Find the number of pairs with given GCD and LCM represented by prime factorization Find the number of pairs with given GCD and LCM represented by prime factorization
Longest Prefix Subsequence matching Fibonacci Sequence Longest Prefix Subsequence matching Fibonacci Sequence
Minimum Operations to Reduce X to Zero Minimum Operations to Reduce X to Zero
Minimum sum of Quotients after performing the given operation Minimum sum of Quotients after performing the given operation
Find Next Optimal Range in Array Find Next Optimal Range in Array

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 11



 

Horje