Categoría: Pigeonhole Principle

Encuentre una string binaria de tamaño máximo 3N que contenga al menos 2 strings dadas de tamaño 2N como subsecuencias

Posted on by Rudeus Greyrat

Dadas tres strings binarias a , b y c , cada una de las cuales tiene 2*N caracteres cada una, la tarea es encontrar una string que tenga casi 3*N caracteres tal que al menos dos de las tres strings dadas ocurran como una de las subsecuencias . Ejemplos: Entrada: a = “00”, b = … Continue reading «Encuentre una string binaria de tamaño máximo 3N que contenga al menos 2 strings dadas de tamaño 2N como subsecuencias»

Matemáticas | El principio del casillero

Posted on by Rudeus Greyrat

Supongamos que una bandada de 20 palomas vuela a un conjunto de 19 casilleros para posarse. Debido a que hay 20 palomas pero solo 19 casilleros, al menos uno de estos 19 casilleros debe tener al menos dos palomas. Para ver por qué esto es cierto, tenga en cuenta que si cada casillero tuviera como … Continue reading «Matemáticas | El principio del casillero»

Clasificación de cuentas | Un algoritmo de clasificación natural

Posted on by Rudeus Greyrat

También conocido como Gravity sort, este algoritmo se inspiró en fenómenos naturales y se diseñó teniendo en cuenta los objetos (o cuentas) que caen bajo la influencia de la gravedad. La idea: los números positivos están representados por un conjunto de cuentas como las de un ábaco. Clasificación de {7, 2, 1, 4, 2} usando … Continue reading «Clasificación de cuentas | Un algoritmo de clasificación natural»

Comprueba si un número S puede hacerse divisible por D sumando repetidamente el resto a S

Posted on by Rudeus Greyrat

Dados dos enteros S y D , la tarea es verificar si el entero S puede hacerse divisible por D o no sumando repetidamente S módulo D a S. Si S es divisible por D , imprima “Sí” . De lo contrario, escriba “No” . Ejemplos: Entrada: S = 3, D = 6 Salida: Sí … Continue reading «Comprueba si un número S puede hacerse divisible por D sumando repetidamente el resto a S»

Matemáticas | Conceptos básicos de combinatoria

Posted on by Rudeus Greyrat

La combinatoria es la rama de las Matemáticas que se ocupa del estudio de las estructuras discretas finitas o contables. Incluye la enumeración o conteo de objetos que tienen ciertas propiedades. Contar nos ayuda a resolver varios tipos de problemas, como contar la cantidad de direcciones IPv4 o IPv6 disponibles.  Principios de conteo – Hay … Continue reading «Matemáticas | Conceptos básicos de combinatoria»

Clasificación de casillero

Posted on by Rudeus Greyrat

La clasificación por casilleros es un algoritmo de clasificación que es adecuado para clasificar listas de elementos donde el número de elementos y el número de valores clave posibles son aproximadamente los mismos. Requiere tiempo O ( n + Rango ), donde n es el número de elementos en la array de entrada y ‘Rango’ es … Continue reading «Clasificación de casillero»

Número mínimo de calcetines requeridos para tener al menos K pares del mismo color

Posted on by Rudeus Greyrat

Dada una array arr[] que consta de N enteros tales que arr[i] representa el número de calcetines del color i y un entero K , la tarea es encontrar el número mínimo de calcetines necesarios para obtener al menos K pares de calcetines del mismo color. Ejemplos: Entrada: arr[] = {3, 4, 5, 3}, K … Continue reading «Número mínimo de calcetines requeridos para tener al menos K pares del mismo color»

Recuento de subarreglos de tamaño K que tienen al menos un par con diferencia absoluta divisible por K-1

Posted on by Rudeus Greyrat

Dado un arr[] que consta de N elementos, la tarea es contar todos los subarreglos de tamaño K que tengan al menos un par cuya diferencia absoluta sea divisible por K – 1 . Ejemplos:   Entrada: arr[] = {1, 5, 3, 2, 17, 18}, K = 4  Salida: 3  Explicación:  Los tres subarreglos de tamaño … Continue reading «Recuento de subarreglos de tamaño K que tienen al menos un par con diferencia absoluta divisible por K-1»

Subconjunto más grande con la suma de cada par como primo

Posted on by Rudeus Greyrat

Dada una array A[], encuentre un subconjunto de tamaño máximo en el que la suma de cada par de elementos sea un número primo. Imprime su longitud y el subconjunto. Considere muchas consultas para diferentes arrays y el valor máximo de un elemento como 100000. Ejemplos:  Input : A[] = {2, 1, 2} Output : … Continue reading «Subconjunto más grande con la suma de cada par como primo»

Máxima diferencia adyacente en una array en su forma ordenada

Posted on by Rudeus Greyrat

Dada una array, encuentre la diferencia máxima entre sus dos elementos consecutivos en su forma ordenada. Ejemplos:  Input: arr[] = {1, 10, 5} Output: 5 Sorted array would be {1, 5, 10} and maximum adjacent difference would be 10 – 5 = 5 Input: arr[] = {2, 4, 8, 11} Output: 4 Solución ingenua: Primero … Continue reading «Máxima diferencia adyacente en una array en su forma ordenada»