13 junio 2007

Solución: Los números binarios

El otro día propuse un problemilla: Los números binarios. No lo inventé yo, lo leí en algún libro que ahora no recuerdo.

Vamos a ver la solución con la siguiente lista de números

1 1 1
0 0 0
1 0 0
1 0 1
0 1 0
0 0 1
0 1 1

¿Que número de 3 dígitos binarios falta?

La solución es:

Tienes un vector con tantos enteros como dígitos tienen los números, inicialmente en todas las posiciones ponemos 0.

Vector: 0 0 0

Ahora vamos leyendo los números uno a uno y sumamos 1 en las posiciones de nuestro vector para las que haya un 1 en el número que hemos leído.

Al leer los primeros números

Número: 1 1 1
Vector: 1 1 1

Número: 0 0 0
Vector: 1 1 1

Número: 1 0 0
Vector: 2 1 1

Cuándo hemos acabado de leer todos los números obtenemos el siguiente vector:

Vector: 3 3 4

Y cómo sabemos que tiene que haber en total igual número 1 en todas las posiciones deducimos que el número que falta es:

Número: 1 1 0




Pablo ha dado con una solución bastante buena que serviría para todo tipo de números, da igual si son o no binarios. Sólo hay que tener cuidado con un detalle: si empezamos a sumar muchísimos números grandes al final no cabrán en un entero y se desbordará.