lunes, 16 de noviembre de 2009

Desafío: Números perdidos

Este problema, desde mi punto de vista, permite motivar el gusto por los algoritmos para resolver los problemas y también permite entender porque es necesario optimizar las soluciones (Este problema lo expuse en las 2 ponencias sobre concursos de programación que tuve en Perú).

Imaginen que tienen 999999 números con valores entre [1..1000000]. Los 999999 números son diferentes, por lo tanto está faltando un número dentro de ese rango. ¿Qué algoritmo se puede hacer para encontrar dicho número utilizando memoria adicional constante (osea sin utilizar otros vectores)?

La solución no es dificil, basta saber aplicar teorias de las sumas de los "N" primeros números naturales... ¿llegaron a la solución? (debe ser una solución linear).

Ahora, ¿qué harían si son 2 números los faltantes? ¿Cómo sabrian cuales faltan?

¿Pueden generalizar su solución para "n" números faltantes?

Buena suerte y diviertanse.

10 comentarios:

  1. Bueno, para 2 números faltantes, haría dos ecuaciones, la primera considerando la suma de todos los elementos y la segunda considerando la suma de los cuadrados y de ahí resolvería el sistema. Para N... déjame pensarlo...

    ResponderEliminar
  2. Si, lo único de lo que tendrias que tener cuidado es de usasr enteros de 64 bits, pues 1000000 al cuadrado ya te da 10^12.
    Por otro lado, la solución del sistema de ecuaciones:
    a+b = S
    a^2 + b^2 = C
    No me parece trivial, pero si se podria despejar a en funcion de S, C y b, dando una solución lineal al problema.
    Otro problema con esa solución es que no funciona para N números faltantes.

    Saludos

    ResponderEliminar
  3. Si pues es un problema muy interesante. Un amigo y yo lo resolvimos asi:

    Calculamos la suma de 1 a 1000000 (con formula) y le restamos la suma de los elementos del vector. Asi conseguimos la suma de los numeros que faltan (llamemosles A y B). Sea A < B entonces se cumple que A < (A+B)/2. Ahora calculamos la suma de 1 a ((A+B)/2 - 1) y le restamos la suma de los elementos del vector menores a (A+B)/2 consiguiendo así el valor de A. Para calcular B restamos el valor de A a la suma A+B previamente calculada.

    Se demora mas pues tiene que recorrer 2 veces el vector sin embargo no tendria problemas con los limites de una variable entera.

    Bueno me quedo pensando como generalizarlo para N numeros perdidos.

    Saludos.

    ResponderEliminar
  4. Otra manera, nlogn (n=todos los numeros), y con memoria auxiliar igual a N (numeros faltantes) es ordenar la lista que te dan y de ahí calcular cuáles faltan

    ResponderEliminar
  5. En realidad hasta podrias ir imprimiendo los números mientras recorres el arreglo ordenado. Osea, imprimes aquellos rangos que son "huecos". En ese caso no necesitarias la memoria auxiliar, pero el algoritmo continua siendo O(N*logN).

    ResponderEliminar
  6. Bueno, para varios numeros.. si quieres ahorrar tiempo teniendo buena memoria..creo que tambien sale linear..
    Tu tienes N numeros y te faltan n, y tienes entre [1 .. N+n] numeros diferentes, usando una estructura para marcar que no gaste mucha memoria como bitset, alguna lista, etc..
    Donde tengas "N+n" elementos esa lista sin marcar, luego recorres los "N" que tienes y vas marcando cual ya tienes..luego al final..recorrer de nuevo y mostrar los que no marcaste..mi solucion linear.
    Saludos

    ResponderEliminar
  7. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  8. Para ordenenar rapidamente se puede aprovechar que los numeros corresponden a sus indices en un vector. Asi se puede ordenar el vector en un solo recorrido o mejor aun mientras se lee los datos colocarlos en la posicion que les corresponde :).

    ResponderEliminar
  9. Las dos soluciones son casi las mismas, con complejidad O(2*N) (Un recorrido para marcar los numeros que presentes y otro para encontrar los que faltan), con memoria adicional O(N).

    Ahora, si vemos que nos faltan n números, podriamos tener suma de los n números con la estrategia original:
    a1+a2+...+an = S
    Luego, sabemos que "ai" esta en el rango [S/(i-1)*n , S/(i*n)], entonces podriamos recorrer de nuevo el arreglo sumando todos los números en cada rango de i y luego hallar todos los números que faltan. Complejidad linear O(2*n), Complejidad en memoria O(n) (para almacenar las sumas en cada rango).

    Luego, si N>>n, entonces creo que esta solución seria la mejor por la menor cantidad de memoria. Ahora si n es relativamente grande, ya no vale la pena y seria mejor hacer un bitset o un arreglo de flags como ya fue comentado.

    Saludos

    ResponderEliminar
  10. sólo quería saludarte primo, bien con el blog y suerte... no me interesa el problema planteado, bastante tengo con mi vida, jajaja.

    ResponderEliminar