{"id":572,"date":"2005-02-27T12:00:00","date_gmt":"2005-02-27T19:00:00","guid":{"rendered":"http:\/\/kodegeek.com\/blog\/?p=572"},"modified":"2005-02-27T12:00:00","modified_gmt":"2005-02-27T19:00:00","slug":"echando-codigo-%c2%bfcomo-obtener-un-numero-de-una-secuencia-rapidamente","status":"publish","type":"post","link":"http:\/\/kodegeek.com\/blog\/2005\/02\/27\/echando-codigo-%c2%bfcomo-obtener-un-numero-de-una-secuencia-rapidamente\/","title":{"rendered":"Echando c\u00f3digo: \u00bfComo obtener un n\u00famero de una secuencia, r\u00e1pidamente?"},"content":{"rendered":"

Les tengo un problemita: Suponga que a usted le dan una secuencia desordenada de n\u00fameros (un arreglo de enteros<\/span>), desde el 1 hasta el 1000, con uno de ellos perdido en la secuencia. Le piden (si, siempre alguien le pide algo ;)) que diga que n\u00famero est\u00e1 perdido. Obviamente puede utilizar la computadora, pero tiene una restricci\u00f3n: No puede crear estructura de datos adicionales, como por ejemplo la lista de n\u00fameros ordenada para buscar el n\u00famero perdido.
<\/span>
\u00bfPiensa que es in\u00fatil?. Pienselo otra vez, esto lo preguntan en entrevistas de vez en cuando y no es tan dificil de resolver.<\/p>\n

Una pista<\/span>: Una forma de resolverlo ser\u00eda marcar que n\u00fameros est\u00e1n en la secuencia, para luego volver a revisar (esta vez contando desde 1 hasta 1000) y as\u00ed ver quien falta. Sin embargo esto es muy ineficiente ya que hay que contar dos veces, adem\u00e1s de hay que almacenar que n\u00fameros fueron visitados.
Pista dos<\/span>: Empiece con una lista m\u00e1s peque\u00f1a, a ver si logra obtener un algoritmo.<\/p>\n

No siga leyendo, pienselo un poco m\u00e1s…<\/p>\n

OK, ya se rindio. Que chimbo :). Bueno, la soluci\u00f3n es simple: Usted puede saber cual es la suma teorica de todos los n\u00fameros de 1 hasta 1000, y si usted suma la secuencia que le dieron y resta ambas sumas entonces all\u00ed est\u00e1 su n\u00famero. Para optimizar m\u00e1s el algoritmo, usted puede calcular la suma de una secuencia conocida con la siguente formula:<\/p>\n

suma = n(n+1)\/2, donde n es el n\u00famero m\u00e1s grande de la secuencia.<\/p><\/blockquote>\n

As\u00ed, para n=1000 tenemos que suma = 500000.<\/p>\n

Aqui le dejo un pedazo de c\u00f3digo en Java (la l\u00f3gica es la misma en cualquier lenguaje):<\/p>\n