martes, 30 de noviembre de 2010

Números que faltan (solución lineal)

Este problema inicialmente se trataba de determinar el numero que faltaba en un conjunto de n-1 elementos donde todos eran diferentes y tomaban valores entre 1 y n inclusive. Es decir en el conjunto faltaba un numero x para que la serie 1, 2, 3, ..., n este completa.

La solución lineal a este problema era calculando la suma de los n primeros números naturales usando la formula:

1 + 2 + 3 + ... + n = (n*(n+1))/2

Y luego a la suma se le iban restando los números que teníamos en el conjunto. Luego de restar todos los elementos lo que nos quedaba era el valor del numero que faltaba.

¿Pero como seria la solución si faltaran no uno sino dos elementos en la serie? Una solución a esta variación del problema anterior era obteniendo dos relaciones: la suma y el producto de los n primeros naturales. Luego ya se puede resolver el sistema de dos ecuaciones y dos variables. Sin embargo hay un problema de implementación, cuando el vector es muy grande el producto de sus elementos podría no entrar en los 4 bytes de una variable entera.

Este problema se nos propuso, ya hace mucho tiempo, en una charla de motivación sobre concursos de programación. Y a la salida mi amigo misterio y yo pensamos en una solución diferente pero sin dejar de ser lineal. Y es la que comentare a continuación:

El primero paso fue calcular la suma "S" de los dos números que faltaban. Eso se consigue aplicando la misma operación del problema original cuando solo faltaba 1 numero.

Luego por condición del problema sabemos que los números que faltan son diferentes. Entonces debe haber un mayor "max" y un menor "min". Además min no puede ser mayor que S/2.

Usando la formula antes mencionada calculamos la suma de los S/2 primeros números naturales y con un segundo recorrido del vector le vamos restando los elementos menores o iguales a S/2. Finalmente nos quedara el valor de min. Luego max sera S - min.

Como usamos dos recorridos la complejidad es 2n + k por lo que el algoritmo sigue siendo lineal.

/*
Descripción:
Este programa recibe como entrada N-2 de números distintos de 1 a N
y arroja como resultado los números los números A y B que faltan.

Formato de entrada:
Cada caso de prueba consiste en 2 lineas la primera contiene el numero N
y la segunda contiene los N-2 números diferentes.
El fin de la entrada se representa con un 0 en la primera linea del caso
de prueba.

Ejemplo:
-------------------------------------------------------------------------
10
7 4 1 5 2 3 6 10
9
2 4 7 5 6 8 9
0
-------------------------------------------------------------------------

Formato de salida:
La respuesta a cada caso de prueba es una sola linea con los numeros A y B
(A < B) separados por un espacio simple.

Ejemplo:
-------------------------------------------------------------------------
8 9
1 3
-------------------------------------------------------------------------
*/

#include <stdio.h>

int main(){
 int n, *v;
 
 scanf("%d", &n);
 while(n!=0) {
  int suma = n*(n+1)/2;
  
  v = new int[n-2];
  for(int i=0; i<n-2; i++){
   scanf("%d", &v[i]);
   suma -= v[i];
  }
  
  int aux = suma/2;
  int a = aux*(aux+1)/2;
  
  for(int i=0; i<n-2; i++)
   if(v[i]<=aux) a -= v[i];
  
  printf("%d %d\n", a, suma-a);  
  scanf("%d", &n);
 }
 
 return 0;
}

¿Ahora podrías plantear una solución para cuando falten 3 elementos, o mejor, para cuando falten k elementos con k<=n?

Saludos.

No hay comentarios:

Publicar un comentario