Categoría: Combinatorial

Saltos mínimos para atravesar todos los enteros en el rango [1, N] de modo que el entero pueda saltar i pasos

Posted on by Rudeus Greyrat

Dado un número entero N, la tarea es encontrar los pasos mínimos para visitar todos los números enteros en el rango [1, N] seleccionando cualquier número entero y saltando i pasos en cada i -ésimo salto. Nota: es posible volver a visitar un número entero más de una vez.  Ejemplos: Entrada: N = 6 Salida: … Continue reading «Saltos mínimos para atravesar todos los enteros en el rango [1, N] de modo que el entero pueda saltar i pasos»

Cuente el número de trillizos con un producto igual al número dado con duplicados permitidos | Conjunto-2

Posted on by Rudeus Greyrat

Dada una array de enteros positivos (puede contener duplicados) y un número ‘m’, encuentre el número de tripletes desordenados ((A i , A j , A k ) y (A j , A i , A k ) y otras permutaciones son contados como uno solo) con producto igual a ‘m’.  Ejemplos:  Entrada: arr[] = … Continue reading «Cuente el número de trillizos con un producto igual al número dado con duplicados permitidos | Conjunto-2»

Contar subconjuntos que satisfacen la condición dada

Posted on by Rudeus Greyrat

Dada una array arr[] y un entero x , la tarea es contar el número de subconjuntos de arr[] suma de todos cuyos subconjuntos (individualmente) es divisible por x . Ejemplos:   Entrada: arr[] = {2, 4, 3, 7}, x = 2  Salida: 3  Todos los subconjuntos válidos son {2}, {4} y {2, 4}  {2} => … Continue reading «Contar subconjuntos que satisfacen la condición dada»

Encuentre todos los subconjuntos distintos de un conjunto determinado utilizando el enfoque BitMasking

Posted on by Rudeus Greyrat

Dado un conjunto de enteros positivos, encuentre todos sus subconjuntos. El conjunto no puede contener elementos duplicados, por lo que cualquier subconjunto repetido debe considerarse solo una vez en la salida. Ejemplos:  Input: S = {1, 2, 2} Output: {}, {1}, {2}, {1, 2}, {2, 2}, {1, 2, 2} Explanation: The total subsets of given … Continue reading «Encuentre todos los subconjuntos distintos de un conjunto determinado utilizando el enfoque BitMasking»

Rango lexicográfico de una string usando STL

Posted on by Rudeus Greyrat

Te dan una string, encuentra su rango entre todas sus permutaciones ordenadas lexicográficamente.  Ejemplos: Input : str[] = «acb» Output : Rank = 2 Input : str[] = «string» Output : Rank = 598 Input : str[] = «cba» Output : Rank = 6 Ya hemos discutido soluciones para encontrar el rango lexicográfico de la … Continue reading «Rango lexicográfico de una string usando STL»

Número de lobby

Posted on by Rudeus Greyrat

En matemáticas combinatorias, el número de Lobb L m, n cuenta el número de formas en que n + m paréntesis abiertos pueden organizarse para formar el inicio de una secuencia válida de paréntesis equilibrados. El número de Lobb está parametrizado por dos enteros no negativos m y n con n >= m >= 0. Se … Continue reading «Número de lobby»

Contar strings binarias de longitud N que constan de «11» como substring

Posted on by Rudeus Greyrat

Dado un entero positivo N , la tarea es encontrar el número de strings binarias de longitud N que contiene «11» como substring. Ejemplos: Entrada: N = 2 Salida: 1 Explicación: La única string de longitud 2 que tiene «11» como substring es «11». Entrada: N = 12 Salida: 3719 Enfoque: la idea es derivar … Continue reading «Contar strings binarias de longitud N que constan de «11» como substring»

Índice máximo que un puntero puede alcanzar en N pasos evitando un índice B dado

Posted on by Rudeus Greyrat

Dados dos números enteros N y B , la tarea es imprimir el índice máximo que puede alcanzar un puntero, comenzando desde el índice 0 th en una array de números naturales (es decir, 0, 1, 2, 3, 4, 5…), digamos arr [] , en N pasos sin colocarse en el índice B en ningún … Continue reading «Índice máximo que un puntero puede alcanzar en N pasos evitando un índice B dado»

Cuente números menores que N que contengan dígitos del conjunto dado: Dígito DP

Posted on by Rudeus Greyrat

Dado un número entero N y un conjunto de dígitos D[] , que consta de dígitos de [1, 9]. La tarea es contar los números posibles menores que N , cuyos dígitos son del conjunto de dígitos dado. Ejemplos:  Entrada: D = [“1”, “4”, “9”], N = 10  Salida: 3  Explicación:  Solo hay 3 números … Continue reading «Cuente números menores que N que contengan dígitos del conjunto dado: Dígito DP»

Costo mínimo para generar cualquier permutación de la string dada

Posted on by Rudeus Greyrat

Dada la string str de tamaño N que consiste en los primeros N alfabetos y una array mat[] de tamaño N*N donde mat[i][j] representa el costo de colocar el i -ésimo carácter del alfabeto antes del j -ésimo carácter en la string . La tarea es encontrar el costo mínimo para generar cualquier permutación de … Continue reading «Costo mínimo para generar cualquier permutación de la string dada»