Cambios mínimos de elementos de array para hacer que sus elementos sean de 1 a N

Suponga que le dan una array con N elementos con cualquier valor entero. Debe encontrar la cantidad mínima de elementos de la array que se deben cambiar para que la array tenga todos los valores enteros entre 1 y N (incluido 1, N).
Ejemplos: 
 

Input : arr[] = {1 4 5 3 7}
Output : 1
We need to replace 7 with 2 to satisfy
condition hence minimum changes is 1.

Input : arr[] = {8 55 22 1 3 22 4 5}
Output :3

Insertamos todos los elementos en una tabla hash. Luego iteramos de 1 a N y verificamos si el elemento está presente en la tabla hash. Si no está presente, aumente el conteo. El valor final de conteo serán los cambios mínimos requeridos.
 

// Count minimum changes to make array
// from 1 to n
#include <bits/stdc++.h>
using namespace std;
 
int countChanges(int arr[], int n)
{
    // it will contain all initial elements
    // of array for log(n) complexity searching
    unordered_set<int> s;
 
    // Inserting all elements in a hash table
    for (int i = 0; i < n; i++)
        s.insert(arr[i]);
     
    // Finding elements to be changed
    int count = 0;
    for (int i = 1; i <= n; i++)
        if (s.find(i) == s.end())
            count++;
 
    return count;
}
 
int main()
{
    int arr[] = {8, 55, 22, 1, 3, 22, 4, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << countChanges(arr, n);
    return 0;
}

// Count minimum changes to
// make array from 1 to n
import java.util.Set;
import java.util.HashSet;
 
class GfG
{
     
    static int countChanges(int arr[], int n)
    {
        // It will contain all initial elements
        // of array for log(n) complexity searching
        Set<Integer> s = new HashSet<>();
     
        // Inserting all elements in a hash table
        for (int i = 0; i < n; i++)
            s.add(arr[i]);
         
        // Finding elements to be changed
        int count = 0;
        for (int i = 1; i <= n; i++)
            if (!s.contains(i))
                count++;
     
        return count;
    }
 
    // Driver code
    public static void main(String []args)
    {
         
        int arr[] = {8, 55, 22, 1, 3, 22, 4, 5};
        int n = arr.length;
 
        System.out.println(countChanges(arr, n));
    }
}
 
// This code is contributed by Rituraj Jain

# Count minimum changes to
# make array from 1 to n
 
def countChanges(arr, n):
 
    # it will contain all initial
    # elements of array for log(n)
    # complexity searching
    s = []
 
    # Inserting all elements in a list
    for i in range(n):
        s.append(arr[i])
     
    # Finding elements to be changed
    count = 0
    for i in range(1, n + 1) :
        if i not in s:
            count += 1
 
    return count
 
# Driver Code
if __name__ == "__main__":
    arr = [8, 55, 22, 1, 3, 22, 4, 5]
    n = len(arr)
    print(countChanges(arr, n))
 
# This code is contributed
# by ChitraNayal

// C# program to Count minimum changes to
// make array from 1 to n
using System;
using System.Collections.Generic;
 
class GfG
{
     
    static int countChanges(int []arr, int n)
    {
        // It will contain all initial elements
        // of array for log(n) complexity searching
        HashSet<int> s = new HashSet<int>();
     
        // Inserting all elements in a hash table
        for (int i = 0; i < n; i++)
            s.Add(arr[i]);
         
        // Finding elements to be changed
        int count = 0;
        for (int i = 1; i <= n; i++)
            if (!s.Contains(i))
                count++;
     
        return count;
    }
 
    // Driver code
    public static void Main(String []args)
    {
        int []arr = {8, 55, 22, 1, 3, 22, 4, 5};
        int n = arr.Length;
        Console.WriteLine(countChanges(arr, n));
    }
}
 
// This code is contributed by 29AjayKumar

<?php
// Count minimum changes to
// make array from 1 to n
 
function countChanges(&$arr, $n)
{
    // it will contain all initial
    // elements of array for log(n)
    // complexity searching
    $s = array();
 
    // Inserting all elements
    // in an array
    for ($i = 0; $i < $n; $i++)
        array_push($s, $arr[$i]);
     
    // Finding elements to be changed
    $count = 0;
    for ($i = 1; $i <= $n; $i++)
        if (!in_array($i, $s))
            $count++;
 
    return $count;
}
 
// Driver Code
$arr = array(8, 55, 22, 1, 3, 22, 4, 5);
$n = sizeof($arr);
echo countChanges($arr, $n);
 
// This code is contributed
// by ChitraNayal
?>

<script>
 
// Count minimum changes to
// make array from 1 to n
     
    function countChanges(arr,n)
    {
        // It will contain all initial elements
        // of array for log(n) complexity searching
        let s = new Set();
       
        // Inserting all elements in a hash table
        for (let i = 0; i < n; i++)
            s.add(arr[i]);
           
        // Finding elements to be changed
        let count = 0;
        for (let i = 1; i <= n; i++)
            if (!s.has(i))
                count++;
       
        return count;
    }
     
    // Driver code
    let arr=[8, 55, 22, 1, 3, 22, 4, 5];
    let n = arr.length;
    document.write(countChanges(arr, n));
     
    // This code is contributed by rag2127
     
</script>

3

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