Múltiplo más pequeño de N formado usando el conjunto dado de dígitos

Dado un conjunto de dígitos S y un número entero N , la tarea es encontrar el número entero positivo más pequeño, si existe, que contenga solo los dígitos de S y sea un múltiplo de N. Tenga en cuenta que los dígitos del conjunto se pueden utilizar varias veces. Ejemplos:

Entrada: S[] = {5, 2, 3}, N = 12 Salida: 252 Podemos observar que 252 se forma con {2, 5} y es múltiplo de 12 Entrada: S[] = {1, 3, 5, 7, 9}, N = 2 Salida: -1 Múltiplo de 2 siempre sería un número par, pero a partir del conjunto dado de dígitos no se puede formar un número par.

Un enfoque simple es ordenar el conjunto de dígitos y luego pasar del número más pequeño al más grande formado usando los dígitos dados. Comprobamos cada número si cumple la condición dada. Implementarlo de esta manera resultaría en una complejidad de tiempo exponencial. Un mejor enfoque es utilizar la aritmética modular. Entonces, mantenemos una cola en la que almacenaremos el módulo de los números formados usando un conjunto de dígitos con el número N dado . Inicialmente en la cola, habría (número de un solo dígito) % N pero podemos calcular (número de dos dígitos) % N usando,

New_mod = (Old_mod * 10 + digit) % N

Al usar la expresión anterior, podemos calcular los valores de módulo de números de varios dígitos. Esta es una aplicación de programación dinámica ya que estamos construyendo nuestra solución desde un estado más pequeño a un estado más grande. Mantenemos otro vector para garantizar que el elemento que se insertará en la cola ya esté presente en la cola o no. Utiliza hashing para garantizar la complejidad de tiempo O(1). Usamos otro vector de par que también usa hashing para almacenar los valores y su estructura es

resultado[nuevo_mod] = {elemento_actual_de_la_cola, dígito}

Este vector se usaría para construir la solución:

1. Ordenar el conjunto de dígitos.
2. Inicialice dos vectores dp y result, con INT_MAX y {-1, 0} respectivamente.
3. Inicialice una cola e inserte el dígito % N.
4. Hacer mientras la cola no está vacía.
5. Elimine el valor frontal de la cola y para cada dígito del conjunto, encuentre (número formado) % N usando la expresión escrita anterior.
6. Si no obtuvimos 0 como valor de módulo antes de que la cola esté vacía, entonces el número positivo más pequeño no existe; de ​​lo contrario, rastrear el vector de resultado desde el índice 0 hasta que obtengamos -1 en cualquier índice.
7. Ponga todos estos valores en otro vector e inviértalo.
8. Esta es nuestra solución requerida.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the required number
int findSmallestNumber(vector<int>& arr, int n)
{
 
    // Initialize both vectors with their initial values
    vector<int> dp(n, numeric_limits<int>::max() - 5);
    vector<pair<int, int> > result(n, make_pair(-1, 0));
 
    // Sort the vector of digits
    sort(arr.begin(), arr.end());
 
    // Initialize the queue
    queue<int> q;
    for (auto i : arr) {
        if (i != 0) {
 
            // If modulus value is not present
            // in the queue
            if (dp[i % n] > 1e9) {
 
                // Compute digits modulus given number and
                // update the queue and vectors
                q.push(i % n);
                dp[i % n] = 1;
                result[i % n] = { -1, i };
            }
        }
    }
 
    // While queue is not empty
    while (!q.empty()) {
 
        // Remove the first element of the queue
        int u = q.front();
        q.pop();
        for (auto i : arr) {
 
            // Compute new modulus values by using old queue
            // values and each digit of the set
            int v = (u * 10 + i) % n;
 
            // If value is not present in the queue
            if (dp[u] + 1 < dp[v]) {
                dp[v] = dp[u] + 1;
                q.push(v);
                result[v] = { u, i };
            }
        }
    }
 
    // If required condition can't be satisfied
    if (dp[0] > 1e9)
        return -1;
    else {
 
        // Initialize new vector
        vector<int> ans;
        int u = 0;
        while (u != -1) {
 
            // Constructing the solution by backtracking
            ans.push_back(result[u].second);
            u = result[u].first;
        }
 
        // Reverse the vector
        reverse(ans.begin(), ans.end());
        for (auto i : ans) {
 
            // Return the required number
            return i;
        }
    }
}
 
// Driver code
int main()
{
    vector<int> arr = { 5, 2, 3 };
    int n = 12;
 
    cout << findSmallestNumber(arr, n);
 
    return 0;
}

# Python3 implementation of the approach
 
# Function to return the required number
def findSmallestNumber(arr, n):
  
    # Initialize both vectors with their initial values
    dp = [float('inf')] * n
    result = [(-1, 0)] * n
 
    # Sort the vector of digits
    arr.sort()
 
    # Initialize the queue
    q = []
    for i in arr: 
        if i != 0: 
 
            # If modulus value is not
            # present in the queue
            if dp[i % n] > 10 ** 9: 
 
                # Compute digits modulus given number
                # and update the queue and vectors
                q.append(i % n)
                dp[i % n] = 1
                result[i % n] = -1, i 
              
    # While queue is not empty
    while len(q) > 0:
 
        # Remove the first element of the queue
        u = q.pop(0)
        for i in arr: 
 
            # Compute new modulus values by using old
            # queue values and each digit of the set
            v = (u * 10 + i) % n
 
            # If value is not present in the queue
            if dp[u] + 1 < dp[v]: 
                dp[v] = dp[u] + 1
                q.append(v)
                result[v] = u, i 
 
    # If required condition can't be satisfied
    if dp[0] > 10 ** 9:
        return -1
    else: 
 
        # Initialize new vector
        ans = []
        u = 0
        while u != -1: 
 
            # Constructing the solution by backtracking
            ans.append(result[u][1])
            u = result[u][0]
         
        # Reverse the vector
        ans = ans[::-1]
        for i in ans: 
 
            # Return the required number
            return i
          
# Driver code
if __name__ == "__main__":
  
    arr = [5, 2, 3] 
    n = 12
 
    print(findSmallestNumber(arr, n))
 
# This code is contributed by Rituraj Jain

2

Complejidad de tiempo: O (N * N), ya que estamos usando bucles anidados para atravesar N * N veces. Donde N es el número de elementos de la array.

Espacio auxiliar: O(N), ya que estamos usando espacio extra para dp y queue. Donde N es el número de elementos de la array.