Desafío: Números perdidos

Este problema, desde mi punto de vista, permite motivar el gusto por los algoritmos para resolver los problemas y también permite entender porque es necesario optimizar las soluciones (Este problema lo expuse en las 2 ponencias sobre concursos de programación que tuve en Perú).

Imaginen que tienen 999999 números con valores entre [1..1000000]. Los 999999 números son diferentes, por lo tanto está faltando un número dentro de ese rango. ¿Qué algoritmo se puede hacer para encontrar dicho número utilizando memoria adicional constante (osea sin utilizar otros vectores)?

La solución no es dificil, basta saber aplicar teorias de las sumas de los "N" primeros números naturales... ¿llegaron a la solución? (debe ser una solución linear).

Ahora, ¿qué harían si son 2 números los faltantes? ¿Cómo sabrian cuales faltan?

¿Pueden generalizar su solución para "n" números faltantes?

Buena suerte y diviertanse.