Bueno, suponga que le dan el siguiente problema:<\/p>\n
Tiene una lista desordenada de n\u00fameros de tama\u00f1o N; Cada elemento puede estar entre 0 y N. Le preguntan cual es la forma m\u00e1s r\u00e1pida de saber si dicha lista tiene elementos duplicados, utilizando la menor cantidad de memoria posible y en un tiempo constante.<\/p>\n
\u00bfComo lo resolver\u00eda usted?<\/p>\n
Usted podr\u00eda comenzar resolviendo este problema contando cuantas ocurrencias de cada n\u00famero aparecen en la lista. Para ello podr\u00eda guardarlas en un arreglo asociativo (HashMap) el cual tiene tiempo de accesso constante. Pero el problema es que si usted tiene muchisimos n\u00fameros repetidos, entonces va a gastar memoria que jode…<\/p>\n
Bueno, si alguna vez usted vi\u00f3 corrimiento de bits ala izquierda y mascaras de bits (en la ULA yo lo aprend\u00ed a hacer en una materia que se llama sistemas l\u00f3gicos :)) entonces vera que el algoritmo se puede simplificar bastante simplemente dandole una mascara distinta a cada n\u00famero, guardandolos a todos en una variable entera. Si recuerda bien, cada vez que corremos un bit a la izquierda es como si estuvieramos elevando a la n dicho n\u00famero, donde n es la cantidad de bits que corremos a la izquierda.<\/p>\n
\u00bfFumado? Si, pero el concepto es muy arrecho<\/span> \ud83d\ude00<\/p>\n OK, no siga leyendo, pienselo un rato y vaya al frente de su computadora.<\/span><\/p>\n \u00bfYa termin\u00f3?, Veamos entonces el c\u00f3digo en Java:<\/p>\n