Количество N цифр, имеющих абсолютную разницу между соседними цифрами как K

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

Примеры:

Input: N = 4, K = 8
Output: 3
Explanation: The absolute difference between every consecutive digit of each number is 8. Three possible numbers are 8080, 1919 and 9191.

Input: N = 2, K = 0
Output: 9
Explanation: 11, 22, 33, 44, 55, 66, 77, 88, 99. The absolute difference between every consecutive digit of each number is 0.

Подход: подход основан на рекурсии. Переберите цифры [1, 9] и для каждой цифры подсчитайте N-значное число, имеющее разность абсолютных цифр как K, используя рекурсию. Следующие случаи возникают при рекурсивном вызове функции.

• Базовый случай: для всех однозначных целых чисел, т. е. N = 1, увеличить количество ответов.
• Рекурсивный вызов: если добавление цифры K к цифре единицы сформированного до сих пор числа (num) не превышает 9, то рекурсивно вызовите, уменьшив N и сделав num = (num*10 + num%10 + K) .

if(num % 10 + K ≤ 9) 
   recursive_function(10 * num + (num % 10 + K), N – 1); 

• Если значение K не равно нулю после всех рекурсивных вызовов и если num % 10 ≥ K , то снова рекурсивно вызовите, уменьшив N и обновив num до (10*num + num%10 – K).

if(num % 10 ≥ K) 
    recursive_function(10 * num + num % 10 – K, N – 1)

Ниже приведена реализация описанного выше подхода.

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