Количество способов составить число с максимальным числом K в нем

Даны число N и цифра K , задача состоит в том, чтобы вычислить количество способов составить число с максимальным количеством K в нем, где в операции две соседние цифры N , которые в сумме дают K , обе заменены на К .

Примеры :

Input :N=1454781, K=9
Output : 2
Explanation :9 can occur maximum two times after applying given operation and there are two ways of doing it. Two numbers formed are : 19479 and 14979. 194781 cannot be formed as it contains 9 only once which is not maximum.

Input : N=1007, K=8
Output : 1
Explanation : No operations can be applied on 1007.Thus, the maximum number of 8s that can be present is 0, and there is only one possible such number, which is 1007.

Подход: В решении проблемы помогают следующие наблюдения:

1. Рассматривая число как строку, подстроки формы «ABAB…» , где A+B=K , являются единственными сегментами числа, которые влияют на ответ.
2. Если длина входящей подстроки четна, есть только один способ применить к ним операции, и, следовательно, они не влияют на ответ. Например, если подстрока «ABAB» , ее можно изменить только на «KK» , чтобы получить максимальное количество K в конечном числе.
3. В противном случае будет ⌈L/2⌉ способов получить максимальное количество Ks , где L — длина подстрок. Например, если подстрока «ABABA» , это можно превратить в следующее:
   1. «ККА»
   2. «КАК»
   3. «АКК»

Выполните следующие шаги, чтобы решить проблему:

1. Преобразуйте N в строку, скажем, S .
2. Инициализируйте переменную ans значением 1 , чтобы сохранить окончательный ответ.
3. Пройдите строку S и для каждого текущего индекса i сделайте следующее:
   1. Инициализируйте переменную count значением 1 , чтобы сохранить длину текущего ответа.
   2. Цикл, пока i меньше длины S , а сумма цифр в S[i] и S[i-1] равна K , и делаем следующее:
      1. Увеличение я .
      2. Счетчик приращений.
   3. Если количество нечетное, обновите ответ как ans *(count+1)/2.
4. Возврат ответ .

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

Временная сложность: O (Log ₁₀ N), поскольку количество цифр в N равно Log ₁₀ N.
Вспомогательное пространство: O(1)