Минимизируйте приращения, чтобы сумма цифр N не превышала S

Даны два положительных целых числа N и S . Задача состоит в том, чтобы минимизировать количество приращений числа N (N = N + 1) , необходимых для того, чтобы сумма цифр числа N была меньше или равна S .
ПРИМЕЧАНИЕ. N может содержать до 18 цифр и 1 <= S <= 162 .

Примеры:

Input: N = 600, S = 5
Output: 400
Explanation: Minimum 400 increments are required as the sum of digits of 1000(600 + 400) is less than 5.

Input: N = 345899211156769, S = 20
Output: 100788843231
Explanation: Minimum required increments are 100788843231.

Подход: Ключевое наблюдение здесь заключается в том, что для минимизации суммы цифр любого числа с минимальными приращениями необходимо минимизировать цифры, начинающиеся с единицы. Выполните следующие шаги, чтобы решить данную проблему.

• Для базового случая, если сумма цифр N уже меньше или равна S , то выход равен 0 .
• Инициализируйте переменные, скажем, ans = 0 и p = 1, где ans будет хранить минимально необходимые приращения, а p будет отслеживать разряды цифр, начиная с разряда единиц.
• Запустите цикл через максимальное количество цифр, которое может иметь N (т. е. 18), и найдите последнюю цифру N . Пусть это будет обозначено цифрой . Затем найдите минимальные приращения, необходимые для преобразования этой цифры в 0 . Обозначается скажем, добавить .
  • цифра = (N / p) % 10
  • добавить = р * (10 - цифра)
  • Увеличивайте N и добавляйте на add .
  • Теперь проверьте, является ли сумма цифр N меньше или равной S .
    • Если условие истинно, выйти из цикла и вывести ответ.
    • В противном случае умножьте p на 10, чтобы получить доступ к предпоследней цифре с места единицы N .
• Цикл запускается снова, и те же шаги выполняются до тех пор, пока не будет найден требуемый ответ.
• Вернуть ответ как окончательный ответ.

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

Временная сложность: O(18*logN).

Вспомогательное пространство: O(1).