Categoría: Bit Magic

Convertir Decimal a Hexa-Decimal incluyendo números negativos

Posted on by Rudeus Greyrat

Dado un número N en formato decimal, la tarea es convertirlo a la representación hexadecimal de N como una string. Los números negativos se almacenan en forma de complemento a 2. Ejemplos:   Entrada: N = 134  Salida: 86 Explicación:  134 = 00000000000000000000000010001000 en representación de 32 bits. Agrupando en fragmentos de cuatro tamaños y convirtiendo … Continue reading «Convertir Decimal a Hexa-Decimal incluyendo números negativos»

Problema del vendedor ambulante | Set 1 (Programación Ingenua y Dinámica)

Posted on by Rudeus Greyrat

  Problema del viajante de comercio (TSP):  Dado un conjunto de ciudades y la distancia entre cada par de ciudades, el problema es encontrar la ruta más corta posible que visite cada ciudad exactamente una vez y regrese al punto de partida. Tenga en cuenta la diferencia entre el ciclo hamiltoniano y TSP. El problema … Continue reading «Problema del vendedor ambulante | Set 1 (Programación Ingenua y Dinámica)»

Partición de un conjunto en K subconjuntos con igual suma usando BitMask y DP

Posted on by Rudeus Greyrat

Dada una array de enteros arr[] que consta de N enteros, la tarea es verificar si es posible dividir la array dada en K subconjuntos no vacíos de igual suma, de modo que cada elemento de la array sea parte de un solo subconjunto. Ejemplos:   Entrada: arr[] = {2, 1, 4, 5, 6}, K = … Continue reading «Partición de un conjunto en K subconjuntos con igual suma usando BitMask y DP»

Raíz cuadrada inversa rápida

Posted on by Rudeus Greyrat

La raíz cuadrada inversa rápida es un algoritmo que estima  , el recíproco (o inverso multiplicativo) de la raíz cuadrada de un número de punto flotante de 32 bits x en formato de punto flotante IEEE 754. Calcular raíces cuadradas recíprocas es necesario en muchas aplicaciones, como la normalización de vectores en videojuegos y se … Continue reading «Raíz cuadrada inversa rápida»

Comprobar si la string binaria es múltiplo de 3 mediante DFA

Posted on by Rudeus Greyrat

Dada una string de caracteres binarios, compruebe si es múltiplo de 3 o no. Ejemplos:  Input : 1 0 1 0 Output : NO Explanation : (1 0 1 0) is 10 and hence not a multiple of 3 Input : 1 1 0 0 Output : YES Explanation : (1 1 0 0) is … Continue reading «Comprobar si la string binaria es múltiplo de 3 mediante DFA»

Recuento mínimo de árboles binarios completos de modo que el recuento de hojas sea N

Posted on by Rudeus Greyrat

Dado un número entero N y un número infinito de árboles binarios completos de diferentes profundidades, la tarea es elegir el número mínimo de árboles tal que la suma del recuento de Nodes hoja en cada uno de los árboles sea N . Ejemplo:   Entrada: N = 7  Salida: 3  Los árboles con profundidades 2, … Continue reading «Recuento mínimo de árboles binarios completos de modo que el recuento de hojas sea N»

XOR de un subarreglo (rango de elementos) | conjunto 2

Posted on by Rudeus Greyrat

Dada una array entera arr[] de consultas de tamaño N y Q. Cada consulta tiene la forma (L, R) , donde L y R son índices de la array. La tarea es encontrar el valor XOR del subarreglo arr[L…R] .  Ejemplos:   Entrada: arr[] = {2, 5, 1, 6, 1, 2, 5} consulta[] = {{1, 4}}  … Continue reading «XOR de un subarreglo (rango de elementos) | conjunto 2»

Longitud de ruta más corta entre dos Nodes dados, de modo que los Nodes adyacentes tengan una diferencia de bit 2

Posted on by Rudeus Greyrat

Dado un gráfico no ponderado y no dirigido que consta de N Nodes y dos números enteros a y b . El borde entre dos Nodes cualesquiera existe solo si la diferencia de bits entre ellos es 2 , la tarea es encontrar la longitud del camino más corto entre los Nodes a y b … Continue reading «Longitud de ruta más corta entre dos Nodes dados, de modo que los Nodes adyacentes tengan una diferencia de bit 2»

Compruebe si todos los bits están desactivados en el rango dado

Posted on by Rudeus Greyrat

Dado un número no negativo n y dos valores l y r . El problema es comprobar si todos los bits están desactivados o no en el rango de l a r en la representación binaria de n . Los bits se numeran de derecha a izquierda, es decir, se considera que el bit menos … Continue reading «Compruebe si todos los bits están desactivados en el rango dado»