Encuentre todos los números en el rango [1, N] que no están presentes en el Array dado

Dada una array arr[] de tamaño N, donde arr[i] son ​​números naturales menores o iguales que N , la tarea es encontrar todos los números en el rango [1, N] que no están presentes en la array dada.

Ejemplos:

Entrada: arr[ ] = {5, 5, 4, 4, 2}
Salida: 1 3
Explicación: 
Para todos los números en el rango [1, 5], 1 y 3 no están presentes en la array.

Entrada: arr[ ] = {3, 2, 3, 1}
Salida: 4

Enfoque ingenuo: el enfoque más simple es hacer un hash de cada elemento de la array utilizando cualquier estructura de datos como el diccionario y luego iterar sobre el rango [1, N] e imprimir todos los números que no están presentes en el hash.

d
 

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

Enfoque: el enfoque anterior se puede optimizar aún más marcando el número en la posición arr[i] – 1, negativo para marcar i está presente en la array. Luego imprima todas las posiciones de los elementos de la array que son positivos ya que faltan. Siga los pasos a continuación para resolver el problema:

• Itere sobre la array, arr[] y para cada elemento actual, num realice los siguientes pasos:
  • Actualice arr[abs(num)-1] a -abs(arr[abs(num)-1]).
• Itere sobre la array, arr[] usando la variable i , e imprima el i+1 si arr[i] es positivo.

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

// C++ program for above approach
#include <iostream>
using namespace std;
 
// Function to find the missing numbers
void getMissingNumbers(int arr[], int N)
{
    // traverse the array arr[]
    for (int i = 0; i < N; i++) {
        // Update
        arr[abs(arr[i]) - 1] = -(abs(arr[abs(arr[i]) - 1]));
    }
    // Traverse the array arr[]
    for (int i = 0; i < N; i++) {
        // If Num is not present
        if (arr[i] > 0)
            cout << i + 1 << " ";
    }
}
 
// Driver Code
int main()
{
 
    // Given Input
    int N = 5;
    int arr[] = { 5, 5, 4, 4, 2 };
 
    // Function Call
    getMissingNumbers(arr, N);
    return 0;
}
// This codeis contributed by dwivediyash

// Java program for the above approach
import java.io.*;
 
class GFG
{
   
    // Function to find the missing numbers
    static void getMissingNumbers(int arr[], int N)
    {
       
        // traverse the array arr[]
        for (int i = 0; i < N; i++)
        {
           
            // Update
            arr[Math.abs(arr[i]) - 1]
                = -(Math.abs(arr[Math.abs(arr[i]) - 1]));
        }
       
        // Traverse the array arr[]
        for (int i = 0; i < N; i++)
        {
           
            // If Num is not present
            if (arr[i] > 0)
                System.out.print(i + 1 + " ");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
       
        // Given Input
        int N = 5;
        int arr[] = { 5, 5, 4, 4, 2 };
 
        // Function Call
        getMissingNumbers(arr, N);
    }
}
 
// This code is contributed by Potta Lokesh

# Python program for the above approach
 
# Function to find the missing numbers
def getMissingNumbers(arr):
 
    # Traverse the array arr[]
    for num in arr:
 
        # Update
        arr[abs(num)-1] = -(abs(arr[abs(num)-1]))
 
    # Traverse the array arr[]
    for pos, num in enumerate(arr):
 
        # If Num is not present
        if num > 0:
            print(pos + 1, end =' ')
 
 
# Given Input
arr = [5, 5, 4, 4, 2]
 
# Function Call
getMissingNumbers(arr)

// C# program for above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the missing numbers
static void getMissingNumbers(int []arr, int N)
{
   
    // traverse the array arr[]
    for (int i = 0; i < N; i++)
    {
       
        // Update
        arr[Math.Abs(arr[i]) - 1] = -(Math.Abs(arr[Math.Abs(arr[i]) - 1]));
    }
   
    // Traverse the array arr[]
    for (int i = 0; i < N; i++)
    {
       
        // If Num is not present
        if (arr[i] > 0)
          Console.Write(i + 1 + " ");
    }
}
 
// Driver Code
public static void Main()
{
 
    // Given Input
    int N = 5;
    int []arr = { 5, 5, 4, 4, 2 };
 
    // Function Call
    getMissingNumbers(arr, N);
}
}
 
// This code is contributed by ipg2016107.

<script>
// Javascript program for the above approach
 
// Function to find the missing numbers
function getMissingNumbers(arr){
 
    // Traverse the array arr[]
    for(let num of arr)
        // Update
        arr[Math.abs(num)-1] = -(Math.abs(arr[Math.abs(num)-1]))
 
    // Traverse the array arr[]
    for (pos in arr)
 
        // If Num is not present
        if(arr[pos] > 0)
            document.write(`${parseInt(pos) + 1} `)
}
 
// Given Input
let arr = [5, 5, 4, 4, 2]
 
// Function Call
getMissingNumbers(arr)
 
// This code is contributed by _saurabh_jaiswal.
</script>

1 3 

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