Semanas 17 y 18 Complejidad Matematicas y Bits

Semanas 17 y 18: Complejidad, Matemáticas y Bits

Objetivo

Abrir la fase avanzada con complejidad formal, aritmética básica, manipulación de bits y divide and conquer aplicado.

Estado del Avance Actual

• Problemas implementados acumulados: 125.
• Tests automatizados acumulados: 314.
• Módulo agregado: src/patterns/math_bit.rs.
• Tests agregados: tests/math_bit_test.rs.
• Guía agregada: notes/complexity-cheatsheet.md.

Problemas Implementados

Problema	Patrón	Función
Single Number	XOR	single_number
Missing Number	XOR	missing_number
Number of 1 Bits	Bits	count_ones
Counting Bits	DP + bits	count_bits
Reverse Bits	Bits	reverse_bits
Hamming Distance	XOR + conteo de bits	hamming_distance
Power of Two	Bits	is_power_of_two
Valid Perfect Square	Búsqueda binaria	is_perfect_square
Pow(x, n)	Divide and conquer	fast_pow
Add Binary	Suma con acarreo	add_binary
Plus One	Acarreo decimal	plus_one
GCD	Euclides	gcd
LCM	Euclides	lcm
Factorial Trailing Zeroes	Conteo de factores de 5	trailing_zeroes
Sieve of Eratosthenes	Matemáticas	sieve
Maximum Subarray	Kadane	maximum_subarray
Majority Element	Boyer-Moore	majority_element

Invariantes Clave

• x ^ x = 0 y x ^ 0 = x.
• n & (n - 1) elimina el bit encendido menos significativo.
• La distancia de Hamming entre enteros se reduce a contar bits en a ^ b.
• Una potencia de dos positiva cumple n & (n - 1) == 0.
• En búsqueda binaria numérica, conviene comparar con enteros amplios para evitar desbordamiento.
• En sumas manuales, el acarreo es el estado mínimo que conecta una posición con la siguiente.
• Los ceros finales de n! dependen de cuántas veces aparece el factor 5.
• En Euclides, gcd(a, b) == gcd(b, a % b).
• En Kadane, el mejor subarreglo que termina en i es extender el anterior o empezar en i.

Verificación

Comandos usados:

cargo fmt
cargo test

Resultado esperado: la suite completa debe pasar antes de cerrar el bloque.

Siguiente Paso

Completar un simulacro corto con dos problemas de bits o matemáticas y registrar la retro en notes/review-queue.md.