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.