11 junio 2007

los números binarios

Me he acordado de este problema a mitad de examen de ingeniería de la programación y aquí lo explico...

Tienes una lista de números binarios desde 0000000000 a 1111111111 (números de 10 digitos).

Algo así:
0000000000
0000000001
0000000010
...
1111111101
1111111110
1111111111

Pero no están todos, falta un sólo número en la lista. ¿cómo calcularías cuál falta?

Los números no están ordenados, así que no vale leer uno tras otro y ver si están seguidos.

Además, sólo puedes recorrer la lista una vez, y sólo tienes unos pocos KB de memoria para el programa, ¿cómo lo harías?

Ejemplo simple con 2 bits:

00
01
11

¿Cuál falta? El 10.