Longitud más pequeña del número divisible por K formado usando solo D

Dados 2 enteros D y K, la tarea es encontrar la longitud mínima de un número formado por la repetición de D que será divisible por K. Si no existe tal número, imprima -1 .

Ejemplos:

Entrada: D = 1, K = 37
Salida: 3
Explicación: El número mínimo formado por la repetición de 1 que es divisible por 37 es 111

Entrada: D = 2, K = 36
Salida: -1

Enfoque ingenuo: la idea es seguir formando el número hasta que se vuelva divisible por K o exceda el rango. 

Complejidad de tiempo: O(10^18)
Espacio auxiliar: O(1)

Enfoque eficiente: la idea es almacenar los residuos que se producen al dividir el número con K y almacenar los residuos en una array . Y cuando vuelve a aparecer el mismo resto, se puede concluir que tal número no existe. Siga los pasos a continuación para resolver el problema:

• Inicialice las variables cnt como 0 para almacenar la respuesta y m para almacenar el número.
• Inicialice el vector v[] de tamaño K para almacenar los restos y establezca el valor de v[m] en 1.
• Iterar en un ciclo while y realizar los siguientes pasos
  • Si m es igual a 0, devuelva el valor de cnt como respuesta.
  • Establezca el valor de m como (((m * (10 % k)) % k) + (d % k)) % k.
  • Si v[m] es igual a 1, devuelva -1 ya que no es posible ese número.
  • Establezca el valor de v[m] en 1 y aumente el valor de cnt en 1.
• Después de realizar los pasos anteriores, devuelva el valor de -1.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to form the smallest number
// possible
int smallest(int k, int d)
{
    int cnt = 1;
    int m = d % k;
 
    // Array to mark the remainders
    // counted already
    vector<int> v(k, 0);
    v[m] = 1;
 
    // Iterate over the range
    while (1) {
        if (m == 0)
            return cnt;
        m = (((m * (10 % k)) % k) + (d % k)) % k;
 
        // If that remainder is already found,
        // return -1
        if (v[m] == 1)
            return -1;
        v[m] = 1;
        cnt++;
    }
    return -1;
}
 
// Driver Code
int main()
{
 
    int d = 1;
    int k = 41;
    cout << smallest(k, d);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to form the smallest number
// possible
static int smallest(int k, int d)
{
    int cnt = 1;
    int m = d % k;
 
    // Array to mark the remainders
    // counted already
    int[] v = new int[k];
    Arrays.fill(v, 0);
    v[m] = 1;
 
    // Iterate over the range
    while (1 != 0)
    {
        if (m == 0)
            return cnt;
             
        m = (((m * (10 % k)) % k) + (d % k)) % k;
 
        // If that remainder is already found,
        // return -1
        if (v[m] == 1)
            return -1;
             
        v[m] = 1;
        cnt++;
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int d = 1;
    int k = 41;
     
    System.out.println(smallest(k, d));
}
}
 
// This code is contributed by sanjoy_62

# Python program for the above approach;
 
# Function to form the smallest number
# possible
def smallest(k, d):
    cnt = 1
    m = d % k
 
    # Array to mark the remainders
    # counted already
    v = [0 for i in range(k)];
    v[m] = 1
 
    # Iterate over the range
    while (1):
        if (m == 0):
            return cnt
        m = (((m * (10 % k)) % k) + (d % k)) % k
 
        # If that remainder is already found,
        # return -1
        if (v[m] == 1):
            return -1
        v[m] = 1
        cnt += 1
 
    return -1
 
# Driver Code
d = 1
k = 41
print(smallest(k, d))
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to form the smallest number
// possible
static int smallest(int k, int d)
{
    int cnt = 1;
    int m = d % k;
 
    // Array to mark the remainders
    // counted already
    int [] v = new int[k];
    for(int i=0;i<k;i++)
        v[i] = 0;
    v[m] = 1;
 
    // Iterate over the range
    while (true) {
        if (m == 0)
            return cnt;
        m = (((m * (10 % k)) % k) + (d % k)) % k;
 
        // If that remainder is already found,
        // return -1
        if ( v[m] == 1)
            return -1;
        
        v[m] = 1;
        cnt++;
    }
   // return -1;
}
 
// Driver Code
public static void Main()
{
 
    int d = 1;
    int k = 41;
    Console.Write(smallest(k, d));
}
}
 
// This code is contributed by bgangwar59.

<script>
        // JavaScript program for the above approach;
 
        // Function to form the smallest number
        // possible
        function smallest(k, d) {
            let cnt = 1;
            let m = d % k;
 
            // Array to mark the remainders
            // counted already
            let v = new Array(k).fill(0);
            v[m] = 1;
 
            // Iterate over the range
            while (1) {
                if (m == 0)
                    return cnt;
                m = (((m * (10 % k)) % k) + (d % k)) % k;
 
                // If that remainder is already found,
                // return -1
                if (v[m] == 1)
                    return -1;
                v[m] = 1;
                cnt++;
            }
            return -1;
        }
 
        // Driver Code
        let d = 1;
        let k = 41;
        document.write(smallest(k, d));
         
   // This code is contributed by Potta Lokesh
    </script>

5

Complejidad de Tiempo : O(K)
Espacio Auxiliar : O(K)