Echando código: ¿Como obtener un número de una secuencia, rápidamente?

Les tengo un problemita: Suponga que a usted le dan una secuencia desordenada de números (un arreglo de enteros), 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úmero está perdido. Obviamente puede utilizar la computadora, pero tiene una restricción: No puede crear estructura de datos adicionales, como por ejemplo la lista de números ordenada para buscar el número perdido.

¿Piensa que es inútil?. Pienselo otra vez, esto lo preguntan en entrevistas de vez en cuando y no es tan dificil de resolver.

Una pista: Una forma de resolverlo sería marcar que números están en la secuencia, para luego volver a revisar (esta vez contando desde 1 hasta 1000) y así ver quien falta. Sin embargo esto es muy ineficiente ya que hay que contar dos veces, además de hay que almacenar que números fueron visitados.
Pista dos: Empiece con una lista más pequeña, a ver si logra obtener un algoritmo.

No siga leyendo, pienselo un poco más…

OK, ya se rindio. Que chimbo :). Bueno, la solución es simple: Usted puede saber cual es la suma teorica de todos los números de 1 hasta 1000, y si usted suma la secuencia que le dieron y resta ambas sumas entonces allí está su número. Para optimizar más el algoritmo, usted puede calcular la suma de una secuencia conocida con la siguente formula:

suma = n(n+1)/2, donde n es el número más grande de la secuencia.

Así, para n=1000 tenemos que suma = 500000.

Aqui le dejo un pedazo de código en Java (la lógica es la misma en cualquier lenguaje):

   1:/**
2: * This program shows how to find a missing number on a sequence of numbers
3: * @author Jose V Nunez
4: * @version 0.1 - 02/27/2005
5: * License: GPL
6: * Blog: El Angel Negro - http://elangelnegro.blogspot.com
7: */
8:
9:import java.util.Random;
10:import java.util.ArrayList;
11:
12:public class FindNumber {
13:
14: public static final int MAX_NUMBERS = 1000;
15:
16: /**
17: * Command line processing
18: * @param args - ignored
19: * @throw Throwable
20: */
21: public static final void main(String [] args) throws Throwable {
22:
23: Random ran = new Random();
24: Integer [] numbers = null;
25: ArrayList list = new java.util.ArrayList(MAX_NUMBERS);
26: // Get a list of unique random numbers
27: for (int i=0; i < MAX_NUMBERS - 1; i++) {
28: while (true) {
29: Integer num = new Integer(
30: ran.nextInt(MAX_NUMBERS) + 1);
31: if (! list.contains(num)) {
32: list.add(num);
33: break;
34: }
35: }
36: }
37: System.out.println(list);
38: long teorSum = (MAX_NUMBERS * (MAX_NUMBERS + 1)) / 2;
39: long realSum = 0;
40: numbers = (Integer []) list.toArray(new Integer[0]);
41: // Now get the sum of the real sequence
42: int len = numbers.length;
43: for (int i = 0; i < len ; i++) {
44: realSum += numbers[i].intValue();
45: }
46: System.out.println("The missing number is: " +
47: (teorSum - realSum) );
48:
49: }
50:}

Por ejemplo, para revizar una lista de 10 números:

[josevnz@localhost test]$ javac FindNumber.java -d .
[josevnz@localhost test]$ java FindNumber
[1, 5, 10, 6, 9, 7, 4, 2, 8]
The missing number is: 3
[josevnz@localhost test]$

Y puede bajarse el código de aqui.

7 thoughts on “Echando código: ¿Como obtener un número de una secuencia, rápidamente?

  1. Ay por favor! Un error ortografico lo puede tener cualquiera…pero no cualquiera puede hacer un comentario inteligente a lo planteado aqui…
    anyway, JV, me marean tus posts (los de informatica), yo no entiendo PIZCA de esta vaina, solo me paré por tu casa para decirte que me encantaron las fotos de tus post anteriores….
    Saludos 🙂

  2. Estimado ‘José Luis Restrepo’,

    !Vaya¡, no solamente usted es una de esas personas con poca educación que se oculta detrás de un teclado para descargar su fustración, sino que además no sabe expresar coherentement lo que piensa…

    Por ejemplo, “pedazo” está bien escrito y en cuanto a ‘revisar’ es un pequeña omisión.

    Pero más importante: Se nota a leguas que usted no se molestó ni siquiera en leer el articulo, pero que es excelente manejando correctores ortográficos :).

    Gracias por las correcciones, pero si no tiene nada positivo que aportar o si va a ser grosero, entonces mejor hagalo en otro lado. Este Blog es un lugar para el sano intercambio de ideas, no para ataques verbales y anónimos.

  3. Hola nostalgia, gracias por visitar mi Blog 🙂

    Si, es un lio tratar de mantener un balance de contenido, además de buena gramática; Dentro de poco colocaré más fotografías y cosas que gusten a otro tipo de audiencia.

    Un saludo,

    JV.

  4. Milagros Socorro, reconocida periodista, quien dicta el Taller de Literatura de la Fundación Polar, dijo hace algunos dias: ” Este es el 5º Taller anual que le dicto a profesionales que plasmarán con método los temas que han elegido para desarrollar durante este año, y que serán publicados en el 2006 y disfruto la brillante inteligencia de quienes han pasado por aqui. Esa inteligencia no puede ser opacada por algún error ortográfico que se puede subsanar con un simple corrector, cuya finalidad es precisamente ésa, corregir, eso lo puede hacer cualquiera,hasta una máquina, en cambio el talento, ése…ése no lo tienen todos.”
    Pienso que el Sr. Restrepo debe magnificar los tontos detalles (Virgo con seguridad) y no se ha paseado por el contenido de tu Blog, dónde, sin ningún tipo de egoismo haces llegar a todos tus invaluables conocimientos.

Los comentarios estan cerrados