metodo - sort algorithm c++

El múltiplo más pequeño que tiene solo 0 y 4 como sus dígitos

Question

Dado un número A, encuentre el número más pequeño B, de manera que A * B contenga los dígitos 4 y 0 solamente y los ceros solo deben estar al final, es decir, los números como 404 no son válidos.

Por ejemplo:

| A | B   | A*B |
|---|-----|-----|
| 1 | 4   | 4   |
| 2 | 2   | 4   |
| 3 | 148 | 444 |
| 4 | 1   | 4   |
| 5 | 8   | 40  |

Bueno, intenté la pregunta de esta manera. Mantener una cola de enteros. El número más pequeño posible es 4.

Pop the number (i.e. the front element of the queue) and push the numbers that can be derived from this popped number. 
That is , when we pop 4, we push (4*10) = 40 and (4*10 + 4) = 44 with the constraint that the popped number is not divisible by 10. If it is, push only its next multiple of 10.

Entonces, mi cola será como: 4,40,44,400,440,444, ....

Como estoy extrayendo elementos de la cola, verificaré si es divisible el número A dado. Si es así, simplemente córtalo y el número que aparece es mi resultado deseado.

Como mi número puede ser realmente grande, mantuve una cola de pair<string,int> donde cadena corresponde al number e int corresponde al remainder . Por lo tanto, el resto de la siguiente etapa se puede calcular fácilmente.

Ex:

queue : <"4",4> 
Pop , current result is string : "4" and remainder is lets say prev = 4
check if the last digit is 0 or not (for checking if its a multiple of 10 or not)
If not, then append 0 to this string and remainder as (prev*10)%a and push this pair in the queue. Also, append 4 to this string with remainder as : (prev*10 +4)%a and push. If the last digits is 0, append 0(not 4) and corresponding remainder, push this pair in the queue.

Queue: <"40",(prev*10)%a>, <"44", (prev*10 +4)%a> and so on..

Hasta que el par en el frente de la cola tenga un resto de 0, continuaremos haciendo esto.

Aunque esta mejora pareció ser un poco buena, pero no fue correcta y no pasó todos los casos de prueba. ¿Alguien puede, por favor, aclarar cómo debería resolverse esto de manera óptima? (El rango de A es 10 ^ 10).

Answer 1

Aquí le doy un algoritmo eficiente, es decir, uno que funciona en el tiempo (editar: corrección) polinomio en el valor de A para resolver la pregunta del número A. También doy una prueba de que este número N existe para todos los números A y demuestro que es correcto de mi algoritmo: la prueba muestra que para cualquier número A, la respuesta correcta tiene como máximo A ^ 2 4 en él (y el número de ceros es a lo sumo casi el doble del número de dígitos de A, crudamente). (No sé si A ^ 2 fours es el mejor límite, pero creo que probablemente no esté demasiado lejos). El tiempo de ejecución no será más que un polinomio en el tamaño de A o la salida. (No lo resolví exactamente). Viendo las otras respuestas ahora, es básicamente lo mismo que la respuesta de pasaba por aqui, pero creo que ofrezco una explicación más rigurosa de por qué funciona. (Aunque mi escritura podría mejorarse probablemente ...)

Terminología: En la secuela, voy a decir que a number N has the form {STRING} para indicar que su expansión decimal coincide con una expresión regular {STRING}, aunque no sea una terminología estándar de la teoría de números.

Problema: Dado A, encuentre el entero más pequeño N de la forma "4 + 0 *" tal que N mod A = 0

Paso 1: considere 10 mod A, y en particular la secuencia {10 ^ n mod A} para n = 1,2,3, ...

La primera pregunta obvia es, ¿qué sucede si 10 es el modo A invertible, es decir, 10 es coprime a A, en caso contrario? (Edit: esto no es realmente obvio, pero en el 90% de estas cosas de la teoría elemental de los números, la manera de progresar es hacer un análisis de casos basado en las factorizaciones primarias de los números involucrados y pensar cuándo las cosas son coprime y cuándo comparten factores comunes es a menudo una buena dirección.)

Si 10 no es coprime a A, hay algunas posibilidades. Una es que 10 divide a A, este es un caso tonto. Podemos simplemente dividir A por 10, encontrar la respuesta entonces y multiplicarla por 10. Si eso está descartado, entonces 5 divide A, pero 2 no, o 2 divide A pero 5 no, o A es coprime a 10 .

Supongamos que 5 divide a A, pero 2 no. Si N mod A = 0 tiene la forma anterior, considere N mod 5 - es igual al dígito de orden más bajo desde 5 | 10. Por lo tanto, el dígito de orden más bajo debe ser 0 y no 4, por lo que 10 | N. Es decir, en este caso, cualquier número entero de la forma "4 + 0 *" tal que N mod A = 0, también tenga N mod 2A = 0. Y 10 se divide 2A, lo que significa que podemos reducir a un problema más simple .

Supongamos que 2 divide a A, pero 5 no. Es obvio que 4 de hecho divide cualquier número de la forma "4 + 0 *", por lo que para cualquier número impar A '', el número entero más pequeño N como se describe es el mismo si tomamos A como A'', 2A ''o 4A ''. Supongamos ahora que 8 divide A. Dado que 8 divide cualquier número de la forma "40+", y 8 no divide 4, por un argumento similar al anterior, implica que el número N debe tener cero como su dígito más bajo, entonces si 8 | A, implica que si N mod A = 0, entonces también N mod 5A = 0. Por lo tanto, podemos pasar a este número, y luego extraer una potencia de 10 y reducir a una pregunta más simple.

Por lo tanto podemos restringir la atención al caso de que 10 es coprime a A.

Esto simplifica las cosas porque entonces la teoría de los números elementales (teorema del resto chino) nos dice que 10 es el modo A invertible, es decir, 10 ^ k = 1 mod A para algunos lo suficientemente grandes k. Significa también que podemos ignorar la posibilidad de ceros en los dígitos de N, ya que si X * 10 ^ y = 0 mod A, y 10 es invertible mod A, también debemos tener que X = 0 mod A, lo que Ser una solución más pequeña.

Por lo tanto, una vez que 10 es coprime a A, el entero más pequeño N de la forma "4 + 0 *", de modo que N mod A = 0 es el mismo que el entero más pequeño de la forma "4+", tal que N mod A = 0.

(Además, ahora está claro que siempre existe ALGUNO número N de esta forma que es divisible por A. Por lo tanto, todos estos programas terminan y no hacen un bucle infinito para ninguna entrada :) Porque, podemos hacer un análisis de ganar-ganar. Supongamos que 10 ^ k = 1 mod A. Ahora considere el valor del número decimal K formado exactamente por k 4, modulo a A. Si esto es cero, eso prueba que el número existe y hemos terminado. Si no es cero, entonces diga que es algún valor "a" mod A que no es igual a 0. Sabemos que el número K * 10 ^ k también es igual a "a" mod A, porque 10 ^ k = 1 mod A. Y K * 10 ^ k también tiene la forma que nos importa, y esto es cierto también para K * 10 ^ {ik} para cualquier i. Por lo tanto, si tomamos un número decimal hecho de exactamente A * k 4, debe ser igual a A * a = 0 mod A. Por lo tanto, hemos construido un número N de la forma deseada que es divisible por A.)

Ahora podemos resolver el problema sin fuerza bruta directamente mediante un simple bucle for. Simplemente hacemos un seguimiento del valor "4000000 ... mod A" y el valor "444444 .... mod A" donde los números tienen k dígitos de longitud, y calculamos estos valores de módulo para k + 1 dígito números por, multiplicando el valor del primero por el valor de 10 mod A, reduciendo el módulo A, luego agregando esto también al segundo y reduciendo ese módulo A.

Aquí está el código completo:

#include <cassert>
#include <iostream>

typedef unsigned long long ul;

ul fast_finder(ul A) {
  assert(A);
  ul num_zeros = 0; // remember how many zeros we need to add at the end

  while ((A % 10) == 0) {
    A /= 10;
    ++num_zeros;
  }

  while ((A % 5) == 0) {
    A /= 5;
    ++num_zeros;
  }

  while ((A % 8) == 0) {
    A /= 2;
    ++num_zeros;
  }

  while ((A % 2) == 0) {
    A /= 2;
  }

  ul four_mod_A = 4 % A;
  ul ten_mod_A = 10 % A;

  ul num_fours = 1;
  // in these variable names "k" is the number of fours we are considering
  ul four_times_ten_to_the_k_mod_A = four_mod_A;
  ul sum_of_fours_mod_A = four_mod_A;
  while (sum_of_fours_mod_A) {
    four_times_ten_to_the_k_mod_A *= 10;
    four_times_ten_to_the_k_mod_A %= A;
    sum_of_fours_mod_A += four_times_ten_to_the_k_mod_A;
    sum_of_fours_mod_A %= A;
    ++num_fours;
  }

  // now build an integer representation of the result from num_fours, num_zeros
  ul result = 0;
  while (num_fours) {
    result *= 10;
    result += 4;
    --num_fours;
  }
  while (num_zeros) {
    result *= 10;
    --num_zeros;
  }
  return result;
}

// This is to check the correctness of the fast algorithm, it''s just the naive algorithm.
ul slow_finder(ul A) {
  assert(A);
  for (ul B = 1;;++B) {
    ul N = B * A;
    bool saw_four = false;
    while (N) {
      ul low = N % 10;
      if (low == 4) {
          saw_four = true;
      } else if (low != 0 || saw_four) { break; }
      N /= 10;
    }
    if (N == 0)
      return A*B;
  }
}

void check(ul x) {
  std::cout << x << ": ";
  ul f = fast_finder(x);
  std::cout << f << std::flush;
  ul s = slow_finder(x);
  if (f != s) {
    std::cout << "failed! ( " << s << " )" << std::endl; return;
  }
  std::cout << ''.'' << std::endl;
}

int main() {
  check(1);
  check(3);
  check(4);
  check(5);
  check(10);
  check(11);
  check(13);
  check(15);
  check(18);
  check(73);
  check(64);
  check(52);
}

Answer 2

Llamemos a los 40 números C , es decir, C = A x B

Dadas las restricciones que tengo, como las entiendo, esto hace que C = AxB del lenguaje 4^n 0^m (no lea esto como 4 a la potencia n , se pretende que se repita 4 n veces ), por lo que solo necesitamos n y m para describir C .

Observaciones:

1. Encontrar el B más pequeño es equivalente a encontrar el C más pequeño que sea un múltiplo de A
2. Cuando dos números C tienen un número diferente de dígitos, la C con el número más alto de dígitos es mayor.
3. Cuando dos números C tienen un número igual de dígitos n + m , la C con el número más alto de 4 s es mayor.

Por lo tanto, hacemos un bucle sobre el número de dígitos en C (comenzando con 1 y aumentando) y sobre el número de 4 s en una C con un número fijo de dígitos, comenzando nuevamente con un solo 4 y aumentando. Esto nos da todos los números C posibles en orden numérico.

Como se señaló y se utilizó en la respuesta de @pasaba por aqui, es posible reducir el espacio de búsqueda haciendo uso del hecho de que A y C pueden compartir factores primos. En este caso, cada C siempre tiene al menos el factor primo 2 ( 2^2 = 4 ) y posiblemente 5 ( 2*5 = 10 ).

De hecho, C = x * 2^(j + 2) * 5^j con x in [1, 11, 111, ...] (es decir, C = x * 4 * 10^j ). La j más pequeña es igual al número más alto de 2 o 5 factores en A Por ejemplo, si A % 25 == 0 , j necesita ser 2 , si A % 400 == 0 , j necesita ser 4 y así sucesivamente.

Vea la respuesta de pasaba por aqui para esa solución.

Versión de fuerza bruta:

#include <cstdint>
#include <iostream>


int
main(int, char *[])
{
    // use uintmax_t and hope that the number still fits.
    uintmax_t = 13ul; // or whatever

    for (unsigned k = 1u;; ++k) {
        // k is the number of digits
        for (unsigned m = 1u; m <= k; ++m) {
            // m is the number of 4s. 
            // We start at one 4 (zero does not make sense)
            uintmax_t C = 0u;
            // build C, add as many 4s as requested and
            // fill up with zeros
            for (unsigned i = 0; i < k; ++i) {
                if (i < m) {
                    C = C * 10 + 4;
                } else {
                    C = C * 10;
                }
            }
            // check if we have a multiple of A
            if (C % A == 0) {
                std::cout << "C = " << C << std::endl;
                std::cout << "B = " << (C / A) << std::endl;
                return 0;
            }
        }
    }

    return 1;
}

Answer 3

Si entiendo el problema, las soluciones deben coincidir con la expresión regular 0 | 4 + 0 *

Hace mucho tiempo que no programo en C, pero el siguiente código podría hacer el truco.

int calc( int n ) {
  int factor5;
  int factor2;
  int j;
  int a;
  int b;
  int i;

  /* trivial case 0 result is 0 */
  if( n==0 ) return 0;

  /* find the number of factors 2 and 5 in n */
  for( a=n, factor5=0; a%5==0; a/=5, factor5++ ); 
  for( a=n, factor2=0; a%2==0; a/=2, factor2++ ); 

  /* result is r=b*a where a=2^(j+2)*5^j */
  j=factor5;
  if( j < factor2-2 ) j=factor2-2; 

  for( a=4,i=0; i<j; i++, a*=10 ); 

  /* generate b in 1, 11, 111, ... until solution found */ 
  for( b=1; (a*b)%n!=0; b=10*b+1 );
  return a*b;
}

Se puede probar con:

int main ( void ) {
  int n,r;

  for( n=0; n<10; n++) {
    r=calc(n); printf( "n=%d r=%d/n", n, r );
  }

  return 0;
}

Nota: Optimícelo. Cambie "int" a "long", "long long" o use un bibliotecario de cualquier número entero de longitud.

Pruebas:

n=0 r=0
n=1 r=4
n=2 r=4
n=3 r=444
n=4 r=4
n=5 r=40
n=6 r=444
n=7 r=444444
n=8 r=40
n=9 r=444444444

Rationalle:

Además del caso trivial 0 con el resultado 0, el resultado "r" debe coincidir con la expresión regular "4 + 0 *": cuatro seguidos de ceros. Es decir, en aritmética normal, r = x * 10 ^ j donde x está en 4,44,444, ....

Si extraemos el factor de 4, tenemos r = x * 4 * 10 ^ j con x en la secuencia 1, 11, 111, .... Tenga en cuenta que los números en esta secuencia nunca tienen factores 2 ni 5 (no son números pares ni terminan con 0 o 5).

En conclusión, r = x * 2 ^ (j + 2) * 5 ^ j, con x en 1, 11, 111, ... y "j" obtenida de la factorización del argumento. El primer paso del programa es calcular "j", luego calcular a = 2 ^ (j + 2) * 5 ^ j, y finalmente generar la secuencia 1, 11, 111, ... y probarla hasta el primer resultado válido.