Подсчитайте числа из заданного диапазона, соседние цифры которых не взаимно просты

Для заданного целого числа N задача вывести количество чисел из диапазона [1, N] , соседние цифры которых не взаимно просты.

Two numbers A and B are said to be co-prime if the GCD of the two numbers is 1.

Примеры:

Input: N = 30
Output: 15
Explanation: The numbers from [1, 30] which have non co-prime adjacent digits are {1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 22, 24, 26, 28, 30}.

Input: N = 10000
Output: 1361

Наивный подход: самый простой подход к решению проблемы состоит в том, чтобы перебрать диапазон от 1 до N и для каждого числа из диапазона проверить, равен ли НОД смежных цифр 1 или нет, и соответствующим образом обновить ответ.

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

Эффективный подход. Описанный выше подход также можно оптимизировать с помощью динамического программирования, поскольку он имеет перекрывающиеся подзадачи и оптимальную подструктуру. Подзадачи могут быть сохранены в таблице dp[][][][] с использованием мемоизации, где dp[i][bound][prev][allZeros] хранит ответ с 'i-й позиции до конца, гдеbound является логической переменной что гарантирует, что число не превышает N , prev сохраняет предыдущую выбранную цифру , allZeros -- это логическая переменная , используемая для проверки того , все ли цифры , выбранные до сих пор , равны 0 или нет .

1. Определите рекурсивную функцию noncoprimeCount(i,bound,prev,allZeros) , выполнив следующие шаги.
   1. Преобразуйте предел N в строку, чтобы он повторялся только по длине строки, а не по фактическому пределу N.
   2. Проверьте базовый случай, то есть, если вся строка пройдена полностью (i == N) , затем верните 1 , поскольку было построено допустимое число в диапазоне [1, N] .
   3. Если результат состояния dp[i][bound][previous][allZeros] уже вычислен, верните значение, хранящееся в dp[i][bound][previous][allZeros].
   4. В текущей позиции 'i' может быть помещено любое число из [0, 9]. При размещении цифры следите за тем, чтобы число не превышало «R» с помощью переменнойbound . Также проверьте, больше ли GCD текущей цифры и предыдущей цифры (которая хранится в prev ), чем 1. Здесь есть два крайних случая:
      1. Если текущий индекс равен 0, поместите любую цифру в первую позицию.
      2. Если все цифры, заполненные до сих пор, являются нулями, т. е . allZeros истинно, то допустимо поместить 1 в текущую позицию, несмотря на то, что НОД (0, 1) = 1 , поскольку это самая значащая цифра. Затем установите для allZeros значение false .
   5. Поместив допустимую цифру в текущую позицию, рекурсивно вызовите функцию noncoprimeCount для элемента с индексом (i + 1).
   6. Верните сумму всех возможных правильных размещений цифр в качестве ответа.

• После выполнения вышеуказанных шагов выведите в качестве результата значение nocoprimeCount(0) .

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

Временная сложность: O (log ₁₀ N * 2 * 10 * 2 * 10). Дополнительный коэффициент 10 возникает, поскольку все цифры [0, 9] повторяются в каждом рекурсивном вызове.
Вспомогательное пространство: O (log ₁₀ N * 2 * 10 * 2)