Наименьшая длина числа, кратного K, образованного с использованием только D

Даны 2 целых числа D и K, задача состоит в том, чтобы найти минимальную длину числа, образованного повторением D , которое будет делиться на K . Если такого числа не существует, выведите -1 .

Примеры:

Input : D = 1, K = 37
Output : 3
Explanation : The minimum number formed by repeating 1 that is divisible by 37 is 111

Input : D = 2, K = 36
Output : -1

Наивный подход: идея состоит в том, чтобы продолжать формировать число до тех пор, пока оно не станет делиться на K или не превысит диапазон.

Сложность времени: O(10^18)
Вспомогательное пространство: O(1)

Эффективный подход: идея состоит в том, чтобы хранить остатки, полученные путем деления числа на K , и сохранять остатки в массиве. И когда тот же остаток появляется снова, можно сделать вывод, что такого числа не существует. Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменные cnt как 0 , чтобы сохранить ответ, и m , чтобы сохранить число.
• Инициализируйте вектор v[] размера K , чтобы сохранить остатки, и установите значение v[m] равным 1.
• Повторите цикл while и выполните следующие шаги.
  • Если m равно 0, то вернуть значение cnt в качестве ответа.
  • Установите значение m как (((m * (10 % k)) % k) + (d % k)) % k.
  • Если v[m] равно 1, то вернуть -1 , так как такое число невозможно.
  • Установите значение v[m] равным 1 и увеличьте значение cnt на 1.
• После выполнения вышеуказанных шагов верните значение -1.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(K)
Вспомогательное пространство: O(K)