Saltar al contenido

Múltiplo máximo de un número donde todos los dígitos son iguales

Ver discusión

Mejorar artículo

Guardar artículo

me gusta el articulo

Ver discusión

Mejorar artículo

Guardar artículo

me gusta el articulo

Dados dos enteros positivos X y Y (1 J 105), encuentre el máximo múltiplo positivo (digamos metro) de X tal que M es menor que 10Y y todos los dígitos en la representación decimal de M son iguales.

Observación: Si no hay un múltiplo positivo que satisfaga las condiciones, devuelve -1.

Ejemplos:

Aporte: X = 1, Y = 6
Salida: 999999
Explicación: 999999 es el entero más grande que es un múltiplo de 1, tiene todos los mismos dígitos y es menor que 106.

Aporte: X = 12, Y = 7
Salida: 888888
Explicación: 888888 es el mayor múltiplo de 12 con todos los dígitos iguales y menos de 107.

Aporte: X = 25, Y = 10
Salida: -1
Explicación: Ningún entero positivo M satisface las condiciones.

Acercarse: Siga la siguiente idea para resolver el problema:

La idea principal es obtener todos los números menores que 10 . para ser consideradoY que tengan los mismos dígitos en representación decimal y verifique si el número es un múltiplo de X, de todos estos múltiplos, devuelva el máximo.

Siga los pasos para resolver el problema:

  • Considere una función f(n, d) que devuelve el resto del número con longitud norte y todos los numeros d cuando se divide por X.
  • Calcula f(n, d) para cada {n, d}.
  • Tenga en cuenta que f(n − 1, d) es un prefijo de f(n, d). Asi que: f(n, d) = (f(n−1, d)*10 + d)%X
  • Encuentre el valor máximo de norte para lo cual f(n, d) = 0.
    • Elige el que tenga el máximo d entre los que tienen el máximo norte.

A continuación encontrará la implementación del enfoque anterior.

C++

 

#include <bits/stdc++.h>

using namespace std;

 

string maxMultiple(int X, int Y)

{

    

    

    pair<int, int> res = { 0, 0 };

    int number = 0;

    for (int d = 1; d <= 9; ++d) {

        for (int n = 1; n <= Y; ++n) {

            number = (10 * number + d) % X;

            if (number == 0)

                res = max(res, { n, d });

        }

    }

 

    

    if (res.first == 0)

        return "-1";

 

    

    

    string ans = "";

    for (int i = 1; i <= res.first; i++)

        ans += (res.second + '0');

 

    return ans;

}

 

int main()

{

    int X = 12, Y = 7;

 

    

    cout << maxMultiple(X, Y);

 

    return 0;

}

Complejidad del tiempo: O(J)
cuarto auxiliar: O(1)