Divide and Conquer – Página 18

Corte todas las varillas con cierta longitud de modo que la suma de la longitud de corte se maximice

julio 5, 2022 Rudeus Greyrat

Dadas N varillas de diferentes longitudes. La tarea es cortar todas las varillas con alguna altura entera máxima ‘h’ tal que la suma de las longitudes de corte de la varilla se maximice y debe ser mayor que M. Imprima -1 si no es posible tal corte. Nota: Una varilla no se puede cortar también. Ejemplos: Entrada: … Continue reading «Corte todas las varillas con cierta longitud de modo que la suma de la longitud de corte se maximice»

Compruebe si la array se puede dividir en subarreglos de modo que el XOR de la longitud de las subsecuencias decrecientes más largas de esos subarreglos sea 0

julio 5, 2022 Rudeus Greyrat

Dada una array de enteros arr[] de tamaño N, la tarea es verificar si arr[] se puede dividir en diferentes subarreglos de modo que al tomar el XOR de longitudes de LDS (subsecuencias decrecientes más largas) de todos los subarreglos sea igual a 0 . Escriba ‘ SÍ ‘ si es posible dividir, de lo … Continue reading «Compruebe si la array se puede dividir en subarreglos de modo que el XOR de la longitud de las subsecuencias decrecientes más largas de esos subarreglos sea 0»

Ordenar por fusión

julio 5, 2022 Rudeus Greyrat

La ordenación por fusiónEl algoritmo es un algoritmo de clasificación que se considera un ejemplo de la estrategia divide y vencerás. Entonces, en este algoritmo, la array se divide inicialmente en dos mitades iguales y luego se combinan de manera ordenada. Podemos pensar en él como un algoritmo recursivo que divide continuamente la array por … Continue reading «Ordenar por fusión»

Encuentre la frecuencia de cada elemento en una array de rango limitado en menos de O (n) tiempo

julio 5, 2022 Rudeus Greyrat

Dada una array ordenada arr[] de enteros positivos, la tarea es encontrar la frecuencia de cada elemento de la array. Suponga que todos los elementos de la array son menores que alguna constante M. Nota: haga esto sin atravesar la array completa. es decir, la complejidad temporal esperada es menor que O(n). Ejemplos: Entrada: arr[] … Continue reading «Encuentre la frecuencia de cada elemento en una array de rango limitado en menos de O (n) tiempo»

Número de formas de dividir un número dado como un conjunto de enteros en orden decreciente

julio 5, 2022 Rudeus Greyrat

Dados dos números y . La tarea es encontrar el número de formas en que a puede representarse mediante un conjunto tal que y la suma de estos números sea igual a a . Además (el tamaño máximo del conjunto no puede exceder m ). Ejemplos : Entrada : a = 4, m = 4 … Continue reading «Número de formas de dividir un número dado como un conjunto de enteros en orden decreciente»

Mediana de dos arreglos ordenados de diferentes tamaños

julio 5, 2022 Rudeus Greyrat

Dados dos arreglos ordenados, a[] y b[], la tarea es encontrar la mediana de estos arreglos ordenados, en complejidad de tiempo O(log n + log m), cuando n es el número de elementos en el primer arreglo, y m es el número de elementos en la segunda array. Esta es una extensión de la mediana de … Continue reading «Mediana de dos arreglos ordenados de diferentes tamaños»

Encuentre el recuento de rotación en la array ordenada rotada

julio 5, 2022 Rudeus Greyrat

Dada una array arr[] de tamaño N que tiene distintos números ordenados en orden creciente y la array se ha rotado a la derecha (es decir, el último elemento se desplazará cíclicamente a la posición inicial de la array) k número de veces, la tarea es encontrar el valor de k . Ejemplos: C++ // … Continue reading «Encuentre el recuento de rotación en la array ordenada rotada»

Encuentre el índice de un elemento adicional presente en una array ordenada

julio 5, 2022 Rudeus Greyrat

Dadas dos arrays ordenadas. Solo hay 1 diferencia entre las arrays. La primera array tiene un elemento adicional agregado en el medio. Encuentre el índice del elemento adicional. Ejemplos: Input: {2, 4, 6, 8, 9, 10, 12}; {2, 4, 6, 8, 10, 12}; Output: 4 Explanation: The first array has an extra element 9. The … Continue reading «Encuentre el índice de un elemento adicional presente en una array ordenada»

Encuentra el número que falta en la progresión aritmética

julio 5, 2022 Rudeus Greyrat

Dada una array que representa elementos de progresión aritmética en orden. Falta un elemento en la progresión, encuentra el número que falta. Ejemplos: C++ // C++ program to find the missing number // in a given arithmetic progression #include<iostream> #include<bits/stdc++.h> using namespace std; int findMissing(int arr[], int n) { int a,d,l,s,i,sum=0,missingnumber; a=arr[0]; l=arr[n-1]; … Continue reading «Encuentra el número que falta en la progresión aritmética»

Consultas para encontrar el peso mínimo de un subárbol de Nodes D-distantes como máximo del Node X

julio 5, 2022 Rudeus Greyrat

Dado un árbol N-ario con raíz en 1 , y una array val[] que consta de pesos asignados a cada Node, y una array Q[][] , que consta de consultas de la forma {X, D} , la tarea para cada consulta es encontrar el mínimo de todos los pesos asignados a los Nodes que están … Continue reading «Consultas para encontrar el peso mínimo de un subárbol de Nodes D-distantes como máximo del Node X»