Recuento de elementos faltantes desde 1 hasta el máximo en el rango de índice [L, R]

Dada una array arr[] de longitud N y una array consultas[] de tamaño Q , la tarea es encontrar el número de elementos faltantes desde 1 hasta el máximo en el rango de índices [L, R] donde L es consultas[i ][0] y R es consultas[i][1] .

Ejemplos:

Entrada: arr[] = {8, 6, 7, 7, 7}, consultas = { {0, 3}, {1, 2}, {0, 2}, {1, 3}, {2, 3} }
Salida: 5 5 5 5 6
Explicación: 
El elemento máximo para el rango [0, 3] es 8, por lo que el número de elementos faltantes es 1, 2, 3, 4, 5.
El elemento máximo para el rango [1, 2] es 7, por lo que el número de elementos que faltan son 1, 2, 3, 4, 5.
El elemento máximo para el rango [0, 2] es 8, por lo que el número de elementos que faltan es 1, 2, 3, 4, 5.
El elemento máximo para el rango [1, 3] es 7, por lo que el número de elementos que faltan es 1, 2, 3, 4, 5.
El elemento máximo para el rango [2, 3] es 7, por lo que el número de elementos que faltan es 1, 2, 3, 4, 5, 6.

Entrada: arr[] = {2, 6, 4, 9}, consultas = { {0, 3}, {1, 2}, {0, 2}, {1, 3}, {2, 3} }
Salida : 5 4 3 6 7
Explicación: 
El elemento máximo para el rango [0, 3] es 9, por lo que el número de elementos que faltan es 1, 3, 5, 7, 8.
El elemento máximo para el rango [1, 2] es 6, por lo que el número de elementos que faltan los elementos son 1, 2, 3, 5.
El elemento máximo para el rango [0, 2] es 6, por lo que el número de elementos faltantes es 1, 3, 5.
El elemento máximo para el rango [1, 3] es 9, por lo que el número de elementos faltantes es 1, 2, 3, 5, 7, 8.
El elemento máximo para el rango [2, 3] es 9, por lo que el número de elementos faltantes es 1, 2, 3, 5, 6, 7, 8.

Enfoque: una forma sencilla es procesar cada consulta de forma lineal, almacenar todos los elementos en un mapa visitado y encontrar el elemento máximo. Luego devuelva el número de elementos que faltan de 1 al máximo en ese rango. 

Siga los pasos a continuación para resolver este problema:

• Tome un mapa desordenado visitado .
• Consultas transversales de i = 0 a Q-1 .
  • Inicialice una variable para almacenar el elemento máximo del rango dado.
  • Ejecute de nuevo un bucle for desde queries[i][0] hasta queries[i][1] .
    • Almacene el elemento máximo en este rango.
    • Haga que la array visitada sea 1 para cada elemento visitado en ese rango.
  • El número de elementos faltantes es el mismo que el valor de ( elemento máximo – número de elementos únicos visitados ).

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

// C++ code to implement above approach.
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the number
// of missing element for each query
vector<int> SolveQMax(int* arr, int& n,
                      int queries[][2], int& q)
{
    // Initializing an unordered map
    unordered_map<int, bool> visited;
    int maxElement;
    vector<int> res;
 
    // Loop to find number of missing elements
    for (int i = 0; i < q; i++) {
        maxElement = INT_MIN;
        visited.clear();
        for (int j = queries[i][0];
             j <= queries[i][1]; j++) {
           
            // Finding the maximum value
            maxElement = max(maxElement,
                             arr[j]);
            visited[arr[j]] = 1;
        }
 
        res.push_back(maxElement
                      - visited.size());
    }
   
    // Return the answer
    return res
}
 
// Driver code
int main()
{
    int N = 5;
    int arr[] = { 8, 6, 7, 7, 7 };
    int Q = 5;
    int queries[][2] = { { 0, 3 }, { 1, 2 },
                         { 0, 2 }, { 1, 3 },
                         { 2, 3 } };
 
    // Function call
    SolveQMax(arr, N, queries, Q);
    return 0;
}

// Java code to implement above approach.
import java.io.*;
import java.util.*;
 
class GFG {
    // Function to find the number
    // of missing element for each query
    public static ArrayList<Integer>
    SolveQMax(int arr[], int n, int queries[][], int q)
    {
        // Initializing an hashmap
        HashMap<Integer, Boolean> visited = new HashMap<>();
        int maxElement;
        ArrayList<Integer> res = new ArrayList<>();
 
        // Loop to find number of missing elements
        for (int i = 0; i < q; i++) {
            maxElement = Integer.MIN_VALUE;
            visited.clear();
            for (int j = queries[i][0]; j <= queries[i][1];
                 j++) {
 
                // Finding the maximum value
                maxElement = Math.max(maxElement, arr[j]);
                visited.put(arr[j], true);
            }
 
            res.add(maxElement - visited.size());
        }
 
        // Return the answer
        return res;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        int arr[] = { 8, 6, 7, 7, 7 };
        int Q = 5;
        int queries[][] = {
            { 0, 3 }, { 1, 2 }, { 0, 2 }, { 1, 3 }, { 2, 3 }
        };
 
        // Function call
        System.out.print(SolveQMax(arr, N, queries, Q));
    }
}
 
// This code is contributed by Rohit Pradhan

# Python code to implement above approach.
 
INT_MIN = -2147483647 - 1
 
# Function to find the number
# of missing element for each query
def SolveQMax(arr, n, queries, q):
         
    # Initializing an unordered map
    visited = {}
    maxElement = INT_MIN
    res = []
 
    # Loop to find number of missing elements
    for i in range(q):
        maxElement = INT_MIN
        visited = {}
        for j in range(queries[i][0],queries[i][1]+1):
 
            # Finding the maximum value
            maxElement = max(maxElement,arr[j])
            visited[arr[j]] = 1
 
        # document.write(Object.keys(visited).length)
        res.append(maxElement - len(visited))
 
    # Return the answer
    return res
 
# Driver code
 
N = 5
arr = [8, 6, 7, 7, 7]
Q = 5
queries = [[0, 3], [1, 2],[0, 2], [1, 3],[2, 3]]
 
# Function call
print(SolveQMax(arr, N, queries, Q))
 
# This code is contributed by shinjanpatra

// C# code to implement above approach.
using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to find the number
    // of missing element for each query
    public static List<int> SolveQMax(int[] arr, int n,
                                      int[,] queries, int q)
    {
       
        // Initializing an hashmap
        Dictionary<int, Boolean> visited = new Dictionary<int, bool>();
        int maxElement;
        List<int> res = new List<int>();
 
        // Loop to find number of missing elements
        for (int i = 0; i < q; i++)
        {
            maxElement = int.MinValue;
            visited.Clear();
            for (int j = queries[i, 0]; j <= queries[i, 1];
                 j++)
            {
 
                // Finding the maximum value
                maxElement = Math.Max(maxElement, arr[j]);
                visited[arr[j]] = true;
            }
 
            res.Add(maxElement - visited.Count);
        }
 
        // Return the answer
        return res;
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 5;
        int[] arr = { 8, 6, 7, 7, 7 };
        int Q = 5;
        int[,] queries = {
            { 0, 3 }, { 1, 2 }, { 0, 2 }, { 1, 3 }, { 2, 3 }
        };
 
        // Function call
        List<int> res = SolveQMax(arr, N, queries, Q);
 
        for (int i = 0; i < res.Count; i++)
        {
            Console.Write(res[i] + " ");
        }
    }
}
 
// This code is contributed by Saurbah Jaiswal

<script>
    // JavaScript code to implement above approach.
    const INT_MIN = -2147483647 - 1;
 
    // Function to find the number
    // of missing element for each query
    const SolveQMax = (arr, n, queries, q) => {
     
        // Initializing an unordered map
        let visited = {};
        let maxElement = INT_MIN;
        let res = [];
 
        // Loop to find number of missing elements
        for (let i = 0; i < q; i++) {
            maxElement = INT_MIN;
            visited = {};
            for (let j = queries[i][0];
                j <= queries[i][1]; j++) {
 
                // Finding the maximum value
                maxElement = Math.max(maxElement,
                    arr[j]);
                visited[arr[j]] = 1;
            }
            // document.write(Object.keys(visited).length)
            res.push(maxElement
                - Object.keys(visited).length);
        }
 
        // Return the answer
        return res
    }
 
    // Driver code
 
    let N = 5;
    let arr = [8, 6, 7, 7, 7];
    let Q = 5;
    let queries = [[0, 3], [1, 2],
    [0, 2], [1, 3],
    [2, 3]];
 
    // Function call
    document.write(SolveQMax(arr, N, queries, Q));
 
// This code is contributed by rakeshsahni
 
</script>

5 5 5 5 6 

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