Análisis Matemático - Find Missing Number

Análisis del Algoritmo findMissingNumber

Pregunta de Investigación

¿El algoritmo findMissingNumber funciona únicamente con números naturales (enteros positivos) o puede manejar otros tipos de enteros? Además: ¿Cómo maneja el algoritmo casos de error y situaciones indeterminadas?

Resultado del Análisis

✅ CONCLUSIÓN: El algoritmo funciona con TODOS los tipos de enteros, no solo números naturales.

🆕 MEJORA IMPORTANTE: El algoritmo ahora retorna *int en lugar de int, permitiendo distinguir entre un resultado válido de 0 y casos de error usando nil.

Casos de Prueba Realizados

Mapa de Cobertura de Pruebas

1. Números Naturales (Positivos)

Rango Número Faltante Elementos Resultado
1-10 5 9 ✅ CORRECTO
1-5 3 4 ✅ CORRECTO
5-15 12 10 ✅ CORRECTO
0-10 5 10 ✅ CORRECTO

2. Números Negativos

Rango Número Faltante Elementos Resultado
-5 a 5 -2 10 ✅ CORRECTO
-10 a -1 -7 9 ✅ CORRECTO
-100 a -90 -95 10 ✅ CORRECTO
-500 a -1 Variable 499 ✅ CORRECTO
-10000 a -5000 Variable 5000 ✅ CORRECTO

3. Secuencias que Cruzan el Cero

Rango Número Faltante Elementos Resultado
-1 a 1 0 2 ✅ CORRECTO
-50 a 50 Variable 100 ✅ CORRECTO

4. Casos de Error y Validación (🆕 NUEVO)

Caso Entrada Retorno Resultado
Slice vacío [] nil ✅ CORRECTO
Un elemento [5] nil ✅ CORRECTO
Dos consecutivos [1, 2] nil ✅ CORRECTO
No consecutivo [1, 3, 5] nil ✅ CORRECTO
Con duplicados [1, 2, 2, 3] nil ✅ CORRECTO
Sin faltante [1, 2, 3, 4, 5] nil ✅ CORRECTO

Explicación Matemática

El algoritmo utiliza la fórmula de suma de secuencias aritméticas:

Representación Matemática

La expresión de la línea 58 del código:

expectedSum := (last - first + 1) * (first + last) / 2

Se representa matemáticamente como:

Sn=n⋅(a1+an)2S_n = \frac{n \cdot (a_1 + a_n)}{2}

🆕 IMPORTANTE: El algoritmo ahora incluye validación del resultado:

missing := expectedSum - sum

if missing < first || missing > last {
    // No missing number in valid range
    return nil
}

return &missing

Esta validación asegura que el número faltante esté dentro del rango válido [first, last].

Donde:

Derivación de la Fórmula

Para una secuencia aritmética consecutiva: a1,a1+1,a1+2,...,ana_1, a_1+1, a_1+2, ..., a_n

Sn=a1+(a1+1)+(a1+2)+...+anS_n = a_1 + (a_1+1) + (a_1+2) + ... + a_n

Aplicando la fórmula de suma aritmética:

Sn=n⋅(primer_término+último_término)2=(an−a1+1)⋅(a1+an)2S_n = \frac{n \cdot (primer\_término + último\_término)}{2} = \frac{(a_n - a_1 + 1) \cdot (a_1 + a_n)}{2}

Esta fórmula es válida para cualquier secuencia aritmética con diferencia común de 1, independientemente de si los números son:

Diagrama de Flujo del Algoritmo

Ejemplo con Números Negativos

Para la secuencia [-5, -4, -3, -1, 0, 1, 2, 3, 4, 5] (falta -2):

Paso Descripción Valor Cálculo
1 Primer término -5 Valor mínimo en la secuencia
2 Último término 5 Valor máximo en la secuencia
3 Número de términos esperados 11 (5 - (-5) + 1) = 11
4 Suma esperada 0 (11 * (-5 + 5)) / 2 = (11 * 0) / 2 = 0
5 Suma actual 2 -5 + (-4) + (-3) + (-1) + 0 + 1 + 2 + 3 + 4 + 5 = 2
6 Número faltante -2 0 - 2 = -2
7 Validación ✅ -2 está en rango [-5, 5]
8 Retorno &(-2) Puntero al valor -2

🆕 Ejemplo de validación fallida:

Para entrada inválida [1, 3, 5, 7] (no consecutiva):

Paso Descripción Valor Resultado
1-5 Cálculos normales missing = -6 Calculado matemáticamente
6 Validación ❌ -6 NO está en rango [1, 7]
7 Retorno nil Error: secuencia inválida

Características del Algoritmo

Complejidad

Funcionamiento Universal

Rendimiento

Los benchmarks muestran un rendimiento excelente y escalable:

Elementos Tiempo de Ejecución Unidad
100 ~100-200 ns
1,000 ~700-800 ns
5,000 ~3.6 µs
1,000,000 ~720 µs

Gráfico de Escalabilidad

Nota: El gráfico muestra la complejidad lineal O(n) del algoritmo con un rendimiento excelente incluso para datasets muy grandes.

Limitaciones Identificadas

  1. Solo funciona con secuencias consecutivas (diferencia común = 1)
  2. Asume que falta exactamente un número
  3. 🆕 Manejo robusto de casos edge:

Recomendaciones

El algoritmo es robusto y universal para encontrar números faltantes en cualquier secuencia de enteros consecutivos, no limitado a números naturales.

🆕 MEJORAS IMPLEMENTADAS:


🔙 ← Volver atrás