JavaScript: un múltiplo de ceros y unos

Hace unos días, apareció por aquí el acertijo Un múltiplo de ceros y unos. En la solución, vimos una manera bastante ingeniosa de encontrar, sea cual sea el número, un múltiplo que esté compuesto únicamente por ceros y unos. En este post, podrás encontrar un modo simple de programar este algoritmo en JavaScript.

Recordemos cómo funcionaba el método general. Se nos da un número n y debemos hallar uno de sus múltiplos (no nulo), que esté compuesto solamente por ceros y por unos. Para ello, construimos la secuencia 1, 11, 111,... hasta llegar al número formado por n+1 unos seguidos. Tenemos, pues, en nuestra lista, n+1 elementos. Anotamos debajo de cada uno de ellos el resto al ser dividido por n. Por construcción, habrá (al menos) dos restos que sean iguales. Tomamos las dos secuencias de unos correspondientes y las restamos. El resultado es la solución al problema.

Veamos ahora cómo implementarlo en JavaScript:

Para empezar nuestro input es un número n. Si te fijas, no necesitamos escribir la lista entera de números de la forma 11...11, porque si encontramos los dos cuyo resto es idéntico, los demás números de después no nos importan ya. Así, tras generar cada uno de esos números y calcular su resto, iremos haciendo la comprobación antes de pasar a generar el siguiente (y detendremos el algoritmo si ya hemos hallado lo que queríamos).

Llamemos a la lista de números formados por unos, de forma poco imaginativa, "listaDeUnos". Al principio, listaDeUnos consiste únicamente en el primero de ellos, 1, e iremos añadiendo más en cada iteración. Por comodidad, definiremos también otra variable "current" que corresponderá al número individual de esa lista con el que trabajamos en la iteración actual. Y también definimos otra lista, "restos", que contendrá los restos al dividir por n de los elementos de listaDeUnos. Al principio, por supuesto, está vacía.

var current = 1, listaDeUnos = [1], restos = [];

Para expresar el bucle, podríamos usar un sinfín de expresiones. Yo he elegido un while con condición "la longitud de listaDeUnos es menor o igual que n+1" (recordemos que sólo queremos n+1 de esos números). Realmente, nunca llegaremos al final de este bucle, porque, por las propiedades de la lista, siempre encontraremos los dos números cuyo resto es idéntico.

while(listaDeUnos.length <= n + 1){
  ...
}

Dentro de este bucle, trabajaremos con cada uno de los números de listaDeUnos. Para empezar, calcularemos su resto al dividirse por n.

  temp = current%n;

Nos saltamos por un momento la condición de salida del bucle y pasamos a meter ese resto en la lista de restos y calcular el siguiente número, que añadiremos a la listaDeUnos.

  ...
  restos.push(temp);
  current = current*10 + 1;
  listaDeUnos.push(current);

Y, ahora sí, examinemos qué debemos poner en esos puntos suspensivos para detener el programa y devolver una solución. La condición "hay dos números con el mismo resto" se traduce aquí a "el resto actual ya aparecía previamente en la lista de restos".

  if(restos.includes(temp)){
    ...
  }

¿Cuáles son los dos números que nos interesan? En primer lugar, current. Y, en segundo, el número que aparece en listaDeUnos en la misma posición que el resto que ya estaba en la lista de restos: listaDeUnos[restos.indexOf(temp)]. Simplemente, debemos restarlos y ya tenemos la solución:

    return current - listaDeUnos[restos.indexOf(temp)];

El programa entero, para que lo puedas leer seguido, sería algo así:

function calcularMultiploCerosUnos(n){
  var current = 1, listaDeUnos = [1], restos = [], temp;
  while(listaDeUnos.length <= n + 1){
    temp = current%n;
    if(restos.includes(temp)){
      return current - listaDeUnos[restos.indexOf(temp)];
    }
    restos.push(temp);
    current = current*10 + 1;
    listaDeUnos.push(current);
  }  
}

Ésta, por supuesto, es sólo una de las maneras posibles de programar este algoritmo. Se podría simplificar un poco el bucle, limpiar variables, etc. Pero me parece que está algo más claro de esta forma.

Puedes jugar un poco con este programa aquí abajo. Introduce un número del cual quieras hallar un múltiplo formado por ceros y unos, y pulsa el botón. ¿Qué ocurre cuando n es demasiado grande? ¿Se te ocurre cómo mejorar el algoritmo para que sea más eficiente?