¿Qué tal usar mapas de bits para grabar, para cada nbr posible? , si se usa o no ese valor?
Para registrar que se toma un valor use SETBIT :
SETBIT key [nbr] 1
Para encontrar un nbr gratuito usa BITPOS :
BITPOS key 0
Para evitar condiciones de carrera, querrás asegurarte de que tu configuración sea atómica. [El OP aborda esto en una pregunta de seguimiento.]
Esto requerirá muy poca memoria (8K bytes para 65536 valores posibles). BITPOS es O(n), pero es poco probable que sea un problema real.
