Dada una array , arr[] de N enteros y 2 enteros L y R , la tarea es devolver el entero más grande K mayor que 0 y L<=K<=R, de modo que ambos valores K y -K existan en la array arr [] . Si no existe tal entero, devuelve 0 . Ejemplos: Aporte:N = … Continue reading «Valor más grande de K tal que tanto K como -K existen en Array en un rango de índice dado [L, R]»
Requisito previo : suma de prefijos – 3D Dada una array tridimensional de enteros arr[L][R][C] (donde L, R y C son dimensiones de la array) y 6 enteros D, E, F, X, Y, Z, encuentre la suma de enteros entre arr[D][E][F] y arr[X][Y][Z] inclusive. Ejemplo: Entrada: A[L][R][C]:{{ { 1, 1, 1, 1 }{ 1, 1, … Continue reading «Encuentre la suma entre las celdas dadas de una array 3D»
Tenemos una array arr[]. Necesitamos encontrar la suma de todos los elementos en el rango L y R donde 0 <= L <= R <= n-1. Considere una situación en la que hay muchas consultas de rango. Ejemplos: Input : 3 7 2 5 8 9 query(0, 5) query(3, 5) query(2, 4) Output : 34 … Continue reading «Consulta de suma de rango usando tabla dispersa»
Dado un árbol N-ario con borde ponderado y consultas Q donde cada consulta contiene dos Nodes del árbol. La tarea es encontrar el borde ponderado máximo en el camino simple entre estos dos Nodes. Ejemplos: Enfoque ingenuo: una solución simple es recorrer todo el árbol para cada consulta y encontrar la ruta entre los dos … Continue reading «Borde máximo ponderado en la ruta entre dos Nodes en un árbol N-ario usando elevación binaria»
Prerrequisitos: Algoritmo de MO , Descomposición SQRT Dada una array arr[] de N elementos y dos números enteros A a B , la tarea es responder Q consultas, cada una de las cuales tiene dos números enteros L y R. Para cada consulta, encuentre el número de elementos en el subarreglo arr[L, R] que se … Continue reading «Consultas de elementos que tienen valores dentro del rango A a B utilizando el algoritmo de MO»
El algoritmo de Mo es un algoritmo genérico. Se puede usar en muchos problemas que requieren el procesamiento de consultas de rango en una array estática , es decir, los valores de la array no cambian entre las consultas. En cada consulta, para un rango dado [a, b], la idea es calcular el valor en … Continue reading «Funcionamiento y necesidad del algoritmo de Mo»
Dada una array de n enteros en orden no decreciente. Encuentre el número de ocurrencias del valor más frecuente dentro de un rango dado. Ejemplos: Input : arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7} Query 1: start = 0, end = 9 Query 2: start = 4, end = 9 … Continue reading «Ocurrencia máxima en un rango dado»
Requisito previo: Introducción y DFS La tarea es encontrar LCA de dos Nodes dados en un árbol (no necesariamente un árbol binario). En publicaciones anteriores, hemos visto cómo calcular LCA utilizando el enfoque Sparse Matrix DP . En esta publicación, veremos una optimización realizada en el método Naive mediante la técnica de descomposición sqrt que … Continue reading «Descomposición Sqrt (o Raíz Cuadrada) | Conjunto 2 (LCA de Tree in O(sqrt(height)) tiempo)»
Dados N rangos de la forma L a R , la tarea es encontrar el entero máximo ocurrido en todos los rangos. Si existe más de uno de estos enteros, imprima el más pequeño. Ejemplos: Entrada: puntos[] = { {1, 6}, {2, 3}, {2, 5}, {3, 8} } Salida: 3 Explicación: 1 ocurre en … Continue reading «Entero máximo ocurrido en n rangos | Conjunto-3»
Dada una array de pares arr[][] de longitud N , y una array queries[] de longitud M , y un entero R , donde cada consulta contiene un entero de 1 a R , la tarea para cada consulta[i] es encontrar el conjunto al que pertenece y encontrar el número total de elementos del conjunto. … Continue reading «Encuentre la array a la que pertenece cada elemento en las consultas dadas junto con el recuento de elementos»