En este artículo, vamos a discutir cómo la técnica Divide and Conquer es útil y cómo podemos resolver el problema con el enfoque de la técnica DAC. En esta sección, discutiremos los siguientes temas. 1. Introduction to DAC. 2. Algorithms under DAC techniques. 3. Recurrence Relation for DAC algorithm. 4. Problems using DAC technique. Divide … Continue reading «Algoritmo divide y vencerás | Introducción – Part 2»
Dada una array de n enteros distintos ordenados en orden ascendente, escriba una función que devuelva un punto fijo en la array, si hay algún punto fijo presente en la array, de lo contrario, devuelve -1. Punto fijo en una array es un índice i tal que arr[i] es igual a i. Tenga en cuenta … Continue reading «Encuentre un punto fijo (valor igual al índice) en una array dada»
Dada una array de 1 y 0 que tiene todos los 1 primero seguidos de todos los 0. Encuentre el número de 0s. Cuente el número de ceros en la array dada. Ejemplos: Input: arr[] = {1, 1, 1, 1, 0, 0} Output: 2 Input: arr[] = {1, 0, 0, 0, 0} Output: 4 Input: … Continue reading «Encuentra el número de ceros – Part 1»
Dada una función ‘int f(unsigned int x)’ que toma un entero no negativo ‘x’ como entrada y devuelve un entero como salida. La función es monótonamente creciente con respecto al valor de x, es decir, el valor de f(x+1) es mayor que f(x) para cada entrada x. Encuentre el valor ‘n’ donde f() se vuelve … Continue reading «Ejemplo de búsqueda binaria ilimitada (encuentre el punto donde una función que aumenta monótonamente se vuelve positiva la primera vez)»
Dada una array arr[] de longitud N y un entero K , la tarea es contar el número de pares (i, j) tales que i < j y arr[i] > K * arr[j] . Ejemplos: Entrada: arr[] = {5, 6, 2, 5}, K = 2 Salida: 2 Explicación: La array consta de dos de estos … Continue reading «Cuente los pares (i, j) de un arreglo dado tal que i < j y arr[i] > K * arr[j]»
Dados n edificios rectangulares en una ciudad bidimensional, calcula el horizonte de estos edificios, eliminando las líneas ocultas. La tarea principal es ver los edificios desde un lado y eliminar todas las secciones que no son visibles. Todos los edificios comparten un fondo común y cada edificio está representado por un triplete (izquierda, altura, derecha) … Continue reading «El problema del horizonte utilizando el algoritmo Divide and Conquer – Part 1»
Dada una array arr[] de tamaño N ( siempre potencia de 2 ), la tarea es encontrar la longitud de la array ordenada más larga a la que se puede reducir la array dada eliminando la mitad de la array en cada operación. Ejemplos: Entrada: arr[] = { 11, 12, 1, 2, 13, 14, 3, … Continue reading «Reduzca la array a la array ordenada más larga posible eliminando la mitad de la array dada en cada operación»
Dada una array arr[] de N enteros y un número de consultas Q . La tarea consiste en responder a tres tipos de consultas. Actualizar [l, r] : por cada i en el rango [l, r] incremente arr[i] en 1 . Actualizar [l, val] : cambia el valor de arr[l] a val . Consulta [l, … Continue reading «Consultas de rango y suma de actualización con factorial»
Dada una array arr[] de N elementos y un entero S . La tarea es encontrar el número mínimo K tal que la suma de los elementos del arreglo no exceda S después de dividir todos los elementos por K . Nota: considere la división de enteros. Ejemplos: Entrada: arr[] = {10, 7, 8, 10, 12, … Continue reading «K mínimo tal que la suma de los elementos de la array después de la división por K no exceda S»
Dada una array ordenada y un valor objetivo, encuentre el primer elemento que sea estrictamente mayor que el elemento dado. Ejemplos: Input : arr[] = {1, 2, 3, 5, 8, 12} Target = 5 Output : 4 (Index of 8) Input : {1, 2, 3, 5, 8, 12} Target = 8 Output : 5 (Index … Continue reading «Primer elemento estrictamente mayor en una array ordenada en Java»