Количество значений, выбранных для X, таких, что N уменьшается до 0 после заданных операций

По заданному натуральному числу N задача состоит в том, чтобы найти количество целых чисел X , которые после выполнения следующей последовательности операций уменьшают значение N до 0 .

• Вычтите значение X из N .
• Если X — однозначное целое число, то прекратите применять операции.
• Обновите значение X как сумму цифр X .

Примеры:

Input: N = 9940
Output: 1
Explanation:
Considering the value of  X  as 9910, the value of N can be reduced to 0 as:

1. Operation 1: Update N as N – X, N = 9939 – 9910 = 30, Update X as sum of digit of X, X = 9 + 9 + 1 + 0 = 19.
2. Operation 2:  Update N as N – X, N = 30 – 19 = 11, Update X as sum of digit of X, X = 9 + 1 = 10.
3. Operation 3: Update N as N – X, N = 11 – 10 = 1, Update X as sum of digit of X, X = 1 + 0 = 1.
4. Operation 4:  Update N as N – X, N = 1 – 1 = 0, Stop applying operations.

Therefore, there exists only one value of X as 1.

Input: N = 9939
Output: 3

Подход: Данная проблема может быть решена с использованием жадного подхода, основанного на следующих наблюдениях:

• Можно заметить, что выбор значения X больше N не уменьшает N до 0 .
• Можно с уверенностью сказать, что если количество цифр в N равно K , то никакое значение X не меньше (N – 10 * K * (K + 1) / 2) и может преобразовать N в 0 .

Из приведенных выше наблюдений идея состоит в том, чтобы перебрать диапазон [N – 10 * K * (K + 1) / 2, N] и подсчитать те значения в этом диапазоне, которые могут преобразовать N в 0 после выполнения заданных операций.

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

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