Subconjunto más grande con M como número faltante más pequeño

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros positivos y un entero positivo M , la tarea es encontrar la longitud del subconjunto más largo cuyo entero faltante más pequeño es M . Si no existe tal subconjunto, imprima «-1» .

Ejemplos: 

Entrada: arr[] = {1, 2, 4}, M = 3 
Salida: 3 
Explicación: 
Los subconjuntos posibles de la array dada son {1}, {2}, {3}, {1, 2}, {2, 4}, {1, 4} y {1, 2, 4}. 
Entre estos, los subconjuntos que contienen elementos en el rango [1, M – 1] pero no M son {1, 2} y {1, 2, 4}. 
Estos subconjuntos contienen 3 como el entero positivo faltante más pequeño. 
Por lo tanto, el subconjunto {1, 2, 4} es el subconjunto requerido más largo con una longitud de 3.

Entrada: arr[] = {2, 2, 3}, M = 4 
Salida: -1 
Explicación: 
El entero positivo faltante más pequeño en la array es 1. 
Por lo tanto, todos los subconjuntos posibles de la array tendrán 1 como el positivo faltante más pequeño entero. 
Por lo tanto, no existe ningún subconjunto con 4 como el número entero mínimo faltante. 
 

Enfoque ingenuo: el enfoque más simple es generar todos los subconjuntos posibles de la array dada y almacenar la longitud máxima entre aquellos subconjuntos cuyo entero mínimo faltante es M. Finalmente, imprime la longitud máxima como respuesta. 

Complejidad temporal: O(N*2 N ) 
Espacio auxiliar: O(N)

Enfoque eficiente: 
Para optimizar el enfoque anterior, tenga en cuenta las siguientes observaciones. Si no falta ningún elemento más pequeño que M en la array, el tamaño del subconjunto más grande será el 1, que consiste en todos los elementos de la array, excepto M. De lo contrario, no es posible  ningún subconjunto con el menor número faltante M.

Siga los pasos a continuación:  

  1. Inserte todos los elementos de la array, excepto M , en el conjunto .
  2. Encuentre la frecuencia de los elementos (digamos, cnt ) en la array arr[] , que no son iguales a M .
  3. Encuentre el número mínimo que falta en el conjunto y, si es igual a M , imprima el valor de cnt como el tamaño máximo del subconjunto.
  4. De lo contrario, imprima «-1» , ya que no es posible ningún subconjunto con el número mínimo faltante como M .

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ Program to implement
// the above approach
 
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
// Function to find and return the
// length of the longest subset
// whose smallest missing value is M
ll findLengthOfMaxSubset(int arr[],
                        int n, int m)
{
    // Initialize a set
    set<int> s;
 
    int answer = 0;
 
    for (int i = 0; i < n; i++) {
 
        int tmp = arr[i];
 
        // If array element is not
        // equal to M
        if (tmp != m) {
 
            // Insert into set
            s.insert(tmp);
 
            // Increment frequency
            answer++;
        }
    }
 
    // Stores minimum missing
    // number
    int min = 1;
 
    // Iterate to find the
    // minimum missing
    // integer
    while (s.count(min)) {
        min++;
    }
 
    // If minimum obtained
    // is less than M
    if (min != m) {
 
        // Update answer
        answer = -1;
    }
 
    // Return answer
    return answer;
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int M = 3;
 
    cout << findLengthOfMaxSubset(
        arr, N, M);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
     
// Function to find and return the
// length of the longest subset
// whose smallest missing value is M
static int findLengthOfMaxSubset(int arr[],
                                int n, int m)
{
     
    // Initialize a set
    Set<Integer> s = new HashSet<>();
 
    int answer = 0;
 
    for(int i = 0; i < n; i++)
    {
        int tmp = arr[i];
 
        // If array element is not
        // equal to M
        if (tmp != m)
        {
             
            // Insert into set
            s.add(tmp);
 
            // Increment frequency
            answer++;
        }
    }
     
    // Stores minimum missing
    // number
    int min = 1;
 
    // Iterate to find the
    // minimum missing
    // integer
    while (s.contains(min))
    {
        min++;
    }
 
    // If minimum obtained
    // is less than M
    if (min != m)
    {
         
        // Update answer
        answer = -1;
    }
 
    // Return answer
    return answer;
}
 
// Driver code
public static void main (String[] args)
{
    int arr[] = { 1, 2, 4 };
    int N = arr.length;
    int M = 3;
     
    System.out.print(findLengthOfMaxSubset(
        arr, N, M));
}
}
 
// This code is contributed by offbeat

Python3

# Python3 program to implement
# the above approach
 
# Function to find and return the
# length of the longest subset
# whose smallest missing value is M
def findLengthOfMaxSubset(arr, n, m):
     
    # Initialize a set
    s = [];
 
    answer = 0;
 
    for i in range(n):
        tmp = arr[i];
 
        # If array element is not
        # equal to M
        if (tmp != m):
 
            # Insert into set
            s.append(tmp);
 
            # Increment frequency
            answer += 1;
 
    # Stores minimum missing
    # number
    min = 1;
 
    # Iterate to find the
    # minimum missing
    # integer
    while (s.count(min)):
        min += 1;
 
    # If minimum obtained
    # is less than M
    if (min != m):
 
        # Update answer
        answer = -1;
 
    # Return answer
    return answer;
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 1, 2, 4 ];
    N = len(arr);
    M = 3;
     
    print(findLengthOfMaxSubset(arr, N, M));
 
# This code is contributed by AnkitRai01

C#

// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
 
class GFG{
     
// Function to find and return the
// length of the longest subset
// whose smallest missing value is M
static int findLengthOfMaxSubset(int []arr,
                                 int n, int m)
{
     
    // Initialize a set
    HashSet<int> s = new HashSet<int>();
 
    int answer = 0;
 
    for(int i = 0; i < n; i++)
    {
        int tmp = arr[i];
 
        // If array element is not
        // equal to M
        if (tmp != m)
        {
             
            // Insert into set
            s.Add(tmp);
 
            // Increment frequency
            answer++;
        }
    }
     
    // Stores minimum missing
    // number
    int min = 1;
 
    // Iterate to find the
    // minimum missing
    // integer
    while (s.Contains(min))
    {
        min++;
    }
 
    // If minimum obtained
    // is less than M
    if (min != m)
    {
         
        // Update answer
        answer = -1;
    }
 
    // Return answer
    return answer;
}
 
// Driver code
public static void Main (string[] args)
{
    int []arr = { 1, 2, 4 };
    int N = arr.Length;
    int M = 3;
     
    Console.Write(findLengthOfMaxSubset(arr, N, M));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program to implement
// the above approach
 
// Function to find and return the
// length of the longest subset
// whose smallest missing value is M
function findLengthOfMaxSubset(arr, n, m)
{
     
    // Initialize a set
    let s = new Set();
 
    let answer = 0;
 
    for(let i = 0; i < n; i++)
    {
        let tmp = arr[i];
 
        // If array element is not
        // equal to M
        if (tmp != m)
        {
 
            // Insert into set
            s.add(tmp);
 
            // Increment frequency
            answer++;
        }
    }
 
    // Stores minimum missing
    // number
    let min = 1;
 
    // Iterate to find the
    // minimum missing
    // integer
    while (s.has(min))
    {
        min++;
    }
 
    // If minimum obtained
    // is less than M
    if (min != m)
    {
         
        // Update answer
        answer = -1;
    }
 
    // Return answer
    return answer;
}
 
// Driver code
let arr = [ 1, 2, 4 ];
let N = arr.length;
let M = 3;
   
document.write(findLengthOfMaxSubset(arr, N, M));
 
// This code is contributed by divyesh072019
 
</script>
Producción: 

3

 

Complejidad Temporal: O(N) 
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
 

Publicación traducida automáticamente

Artículo escrito por madarsh986 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *