Enteros positivos hasta N que no están presentes en el Array dado

Dada una array a[] y un entero N , la tarea es encontrar todos los números naturales del rango [1, N] que no están presentes en la array dada.

Ejemplos:

Entrada: N = 5, a[] = {1, 2, 4, 5}
Salida: 3
Explicación: 3 es el único número entero del rango [1, 5] que no está presente en la array.

Entrada: N = 10, a[] = {1, 3, 4, 6, 8, 10}
Salida: 2 5 7 9

Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar el rango [1, N] y, para cada número del rango, recorrer la array y verificar si está presente en la array o no. 
Complejidad de tiempo: O(N * len), donde len denota la longitud de la array. 
Espacio Auxiliar: O(1)

Enfoque eficiente: el enfoque anterior se puede optimizar utilizando HashSet . Recorra la array dada e inserte todos los elementos de la array en el HashSet . Luego, recorra el rango [1, N] y para cada elemento, verifique si está presente en HashSet o no usando el método contains() , para calcular la búsqueda en complejidad O(1). 
Complejidad temporal: O(N) 
Espacio auxiliar: O(N)
 

Enfoque alternativo: el problema dado se puede resolver usando BitSet en C++ . Siga los pasos a continuación para resolver el problema:

1. Inicialice una variable BitSet , bset con N como longitud.
2. Para cada elemento de la array, establezca su bit en falso, usando bset.set(arr[i]-1, 0) , donde establece el bit en la posición arr[i] – 1 a 0 .
3. Ahora, itere desde bset._Find_first() a bset.size() – 1 usando una variable, digamos i .
4. Imprime i + 1 y configura bset._Find_next() .

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

// CPP program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find positive integers
// from 1 to N that are not present in the array
void findMissingNumbers(int arr[], int len)
{
    const int M = 15;
 
    // Declare bitset
    bitset<M> bset;
 
    // Iterate from 0 to M - 1
    for (int i = 0; i < M; i++) {
        bset.set(i);
    }
 
    // Iterate from 0 to len - 1
    for (int i = 0; i < len; i++) {
        bset.set(arr[i] - 1, 0);
    }
 
    // Iterate from bset._Find_first()
    // to bset.size() - 1
    for (int i = bset._Find_first();
         i < bset.size();
         i = bset._Find_next(i)) {
 
        if (i + 1 > len)
            break;
 
        cout << i + 1 << endl;
    }
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 2, 4, 6, 8, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    findMissingNumbers(arr, n);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
 
    // Function to find positive integers
    // from 1 to N that are not present in the array
    static void findMissingNumbers(int[] arr, int len)
    {
        int M = 15;
 
        // Declare bitset
        BitSet bset = new BitSet(M);
 
        // Iterate from 0 to M - 1
        for (int i = 0; i < M; i++)
        {
            bset.set(i);
        }
 
        // Iterate from 0 to len - 1
        for (int i = 0; i < len; i++)
        {
            bset.set(arr[i] - 1, false);
        }
 
        // Iterate from bset._Find_first()
        // to bset.size() - 1
        for (int i = bset.nextSetBit(0); i >= 0;
             i = bset.nextSetBit(i + 1))
        {
            if (i + 1 > len)
                break;
            System.out.println(i + 1);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int[] arr = new int[] { 1, 2, 4, 6, 8, 9 };
        int n = arr.length;
        findMissingNumbers(arr, n);
    }
}
 
// This code is contributed by Dharanendra L V

# Python 3 program for the above approach
 
#  Function to find positive integers
# from 1 to N that are not present in the array
def findMissingNumbers(arr, n):
 
    M = 15
 
    # Declare bitset
    bset = [0]*M
 
    # Iterate from 0 to M - 1
    for i in range(M):
        bset[i] = i
 
    # Iterate from 0 to n - 1
    for i in range(n):
        bset[arr[i] - 1] = 0
 
    bset = [i for i in bset if i != 0]
 
    # Iterate from bset._Find_first()
    # to bset.size() - 1
 
    for i in range(len(bset)):
 
        if (bset[i] + 1 > n):
            break
 
        print(bset[i] + 1)
 
# Driver Code
if __name__ == "__main__":
 
    arr = [1, 2, 4, 6, 8, 9]
    n = len(arr)
 
    findMissingNumbers(arr, n)
 
    # This code is contributed by ukasp.

// C# program for the above approach
 
using System;
using System.Collections;
 
class GFG
{
 
    // Function to find positive integers
    // from 1 to N that are not present in the array
    static void findMissingNumbers(int[] arr, int len)
    {
        int M = 15;
 
        // Declare bitset
        int[] bset = new int[M];
 
        // Iterate from 0 to M - 1
        for (int i = 0; i < M; i++)
        {
            bset[i] = i;
        }
 
        // Iterate from 0 to len - 1
        for (int i = 0; i < len; i++)
        {
            bset[arr[i] - 1] = 0;
        }
 
        ArrayList temp = new ArrayList();
 
        foreach(int x in bset){
            if(x != 0){
                temp.Add(x);
            }
        }
 
        // Iterate from bset._Find_first()
        // to bset.size() - 1
        for (int i = 0; i < temp.Count; i++)
        {
            if ((int)temp[i] + 1 > len){
                break;
            }
            Console.WriteLine((int)temp[i] + 1);
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = new int[] { 1, 2, 4, 6, 8, 9 };
        int n = arr.Length;
        findMissingNumbers(arr, n);
    }
}
 
// This code is contributed by Saurabh Jaiswal

<script>
 
// JavaScript program for the above approach
 
// Function to find positive integers
// from 1 to N that are not present in the array
function findMissingNumbers(arr, n){
 
    let M = 15
 
    // Declare bitset
    let bset = new Array(M).fill(0)
 
    // Iterate from 0 to M - 1
    for(let i=0;i<M;i++)
        bset[i] = i
 
    // Iterate from 0 to n - 1
    for(let i=0;i<n;i++)
        bset[arr[i] - 1] = 0
 
    bset = bset.filter((i)=>i != 0)
 
 
    // Iterate from bset._Find_first()
    // to bset.size() - 1
    for(let i = 0; i < bset.length; i++)
    {
 
        if (bset[i] + 1 > n)
            break
 
        document.write(bset[i] + 1,"</br>")
   }
}
 
// Driver Code
 
let arr = [1, 2, 4, 6, 8, 9]
let n = arr.length
 
findMissingNumbers(arr, n)
 
// This code is contributed by shinjanpatra
 
</script>

3
5

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