Conteo de strings binarias de longitud N que tienen igual conteo de 0 y 1 y conteo de 1 ≥ conteo de 0 en cada substring de prefijo

Dado un entero N , la tarea es encontrar el número de strings binarias posibles de longitud N con una frecuencia igual de 0 y 1 en las que la frecuencia de 1 sea mayor o igual a la frecuencia de 0 en cada substring de prefijo. Ejemplos: Entrada: N = 2 Salida: 1 Explicación: … Continue reading «Conteo de strings binarias de longitud N que tienen igual conteo de 0 y 1 y conteo de 1 ≥ conteo de 0 en cada substring de prefijo»

Número de arrays bitónicas de longitud n y que constan de elementos de 1 a n

Para un número dado n (n > 1), necesitamos encontrar el número de formas en que puede hacer una array bitónica de longitud n, que consta de todos los elementos del 1 al n. Nota: [1, 2,…n] y [n, n – 1…2, 1] no se consideran arreglos bitónicos.   Ejemplos:  Input : n = 3 Output : … Continue reading «Número de arrays bitónicas de longitud n y que constan de elementos de 1 a n»

Teorema de conteo de órbitas o lema de Burnside

El lema de Burnside también se conoce a veces como teorema de conteo de órbitas . Es uno de los resultados de la teoría de grupos . Se utiliza para contar objetos distintos con respecto a la simetría. Básicamente nos da la fórmula para contar el número total de combinaciones, donde dos objetos que son … Continue reading «Teorema de conteo de órbitas o lema de Burnside»

String lexicográficamente más grande posible por un costo dado de agregar caracteres

Dado un entero W y una array a[] de tamaño 26 donde ai denota el costo de usar el i -ésimo alfabeto, la tarea es encontrar lexicográficamente la string más grande que se puede generar por un costo , W. Ejemplos: Entrada: W = 236, a[] = {1, 1, 2, 33, 4, 6, 9, 7, … Continue reading «String lexicográficamente más grande posible por un costo dado de agregar caracteres»

Número de strings de longitud N sin substring palindrómica

Dados dos enteros positivos N, M . La tarea es encontrar el número de strings de longitud N bajo el conjunto alfabético de tamaño M tal que ninguna substring de tamaño mayor que 1 sea palindrómica. Ejemplos:   Input : N = 2, M = 3 Output : 6 In this case, set of alphabet are … Continue reading «Número de strings de longitud N sin substring palindrómica»

Número de formas en que un elemento vuelve a su posición inicial en N intercambios en una array de tamaño K

Dados dos números K y N , la tarea es encontrar el número de formas en que un elemento en la posición i regresa a su posición inicial en una array de longitud K en N pasos, donde, en cada paso, el elemento puede intercambiarse con cualquier otro elemento en K Ejemplos:  Entrada: N = … Continue reading «Número de formas en que un elemento vuelve a su posición inicial en N intercambios en una array de tamaño K»

Combinaciones con repeticiones

Supongamos que tenemos una string de longitud-n y queremos generar todas las combinaciones/permutaciones tomadas r a la vez con/sin repeticiones. Hay cuatro conceptos fundamentales en Combinatoria 1) Combinaciones sin repeticiones/sustituciones. 2) Combinaciones con repeticiones/sustituciones. 3) Permutaciones sin repeticiones/sustituciones. 4) Permutaciones con repeticiones/sustituciones. A continuación se muestra una tabla resumen que representa los conceptos fundamentales de la Teoría Combinatoria.   … Continue reading «Combinaciones con repeticiones»

Subsecuencia de permutación más larga en una array dada

Dada una array arr que contiene N elementos, encuentre la longitud de la subsecuencia más larga tal que sea una permutación válida de una longitud particular. Si no existe tal secuencia de permutación, imprima 0. Ejemplos:   Entrada: arr[] = {3, 2, 1, 6, 5}  Salida: 3  Explicación:  La subsecuencia de permutación más larga será [3, … Continue reading «Subsecuencia de permutación más larga en una array dada»

Número de formas de seleccionar K número par pequeño desde la izquierda de cada elemento en una array dada

array , arr[] N selecciona K elementos. Entrada: arr[] = {4, 2, 12, 33}, K = 2 Salida: 0 0 1 3 Explicación:  Para arr[0](=4), hay 0, incluso elementos menores que arr[i]. Por lo tanto, las formas de seleccionar 2 elementos de 0 elementos son iguales a C(0, 2) = 0. Para arr[1](=2), hay 0, … Continue reading «Número de formas de seleccionar K número par pequeño desde la izquierda de cada elemento en una array dada»

Suma de Bitwise AND de todos los tripletes desordenados de una array

Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la suma de Bitwise AND de todos los tripletes posibles (arr[i], arr[j], arr[k]) tal que i < j < k . Ejemplos: Entrada: arr[] = {3, 5, 4, 7} Salida: 5 Explicación: Suma de Bitwise AND de todos los tripletes posibles … Continue reading «Suma de Bitwise AND de todos los tripletes desordenados de una array»