El problema proviene de la capacitación en programación de Codility y suena de la siguiente manera: tenemos una matriz (A []) con n (que van de 1 a 100,000) elementos y estos son nuestros parámetros. Los elementos de la matriz son enteros de −2,147,483,648 a 2,147,483,647, y necesitamos encontrar el entero positivo más pequeño que NO esté en la matriz. Por supuesto, esto podría hacerse fácilmente en O (n * log n) clasificándolos todos y revisando la matriz ordenada, buscando el número de posición faltante (esta última operación tiene O (n) peor complejidad de tiempo en mi solución). Pero de acuerdo con Codility, TODO este problema se puede hacer en O (n), y no veo ninguna forma de hacerlo. ¿Podría alguien darme algunos consejos para que me libere?

PD: Aquí hay un enlace a una descripción detallada del problema que no puedo copiar:https://codility.com/c/intro/demo35UEXH-EAT