Минимальная стоимость преобразования 1 в N путем умножения X или вращения цифр вправо

Даны два целых числа N и X , задача состоит в том, чтобы преобразовать 1 в N , используя минимум операций любой из следующих операций:

1. Измените число (скажем, T ) в Т*Х . Это стоит одну единицу.
2. Вращайте число вправо . Это стоит одну единицу.

Примечание. Вращение вправо означает, что последняя цифра числа становится первой, а все остальные цифры сдвигаются вправо. Например, 456 становится 645. Операцию перетасовки вправо нельзя выполнять над однозначными целыми числами или целыми числами, кратными 10.

Примеры:

Input: N = 61, X =4 
Output: 3
Explanation: The sequence of operations is as follows :

• 1 -> 4  (Using first operation -> T*X= 1 * 4 = 4) cost = 1
• 4 -> 16  (Using first operation -> T*X = 4 * 4 = 16) cost = 1 
• 16 -> 61 (Using second operation -> right shuffling 16 -> 61) cost = 1

Hence, the minimum costs required to convert from initial 1 to N is 3.

Input: N = 72, X = 3
Output: 4
Explanation: The sequence of operations is as follows :

• 1 -> 3 (Using first operation -> T*X = 1*3 = 3 ) cost = 1
• 3 -> 9 (Using first operation -> T*X = 3*3 = 9) cost = 1
• 9 -> 27 (Using first operation -> T*X = 9*3 = 27) cost = 1 
• 27 -> 72 (Using second operation -> right shuffling 27 -> 72) cost = 1

Hence, the minimum cost required to convert from initial 1 to N is 4.

Input: N = 5, X = 3
Output: -1
Explanation: It is impossible to reach 5.

Наивный подход: наивный подход заключается в том, чтобы попробовать все возможные комбинации, выполнив операции.

It can be observed that the upper limit of required operations does not exceed value N. So generate all possible values that can be formed using i operations (i in range [1, N]) and check if any of them is equal to N and update  the minimum cost accordingly

Посмотрите здесь, чтобы сгенерировать все возможные комбинации T-операций. Выполните следующие шаги, чтобы решить эту проблему:

• Итерация цикла от T = 1 до N
  • Перебрать все 2 ^T комбинаций возможных чисел, используя T ходов (2 ^T потому что либо выполнить операцию типа 1 или типа 2).
    • Назначьте temp = 1 для хранения сформированного числа
    • Если первая операция не выполнена
      • Назначить темп = темп*Х
    • В противном случае, если temp > 0 и temp не кратно 10
      • Температура правого вращения.
  • Если temp = N , верните T , потому что это минимальная стоимость.
• Если невозможно сформировать число за N шагов, то оно не может быть сформировано (как упоминалось ранее), поэтому верните -1 .

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

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

Эффективный подход: проблема может быть эффективно решена с использованием BFS на основе следующей идеи:

• Build a graph out of the transitions. If we can go from T1 to some T2 using either one of the two operations, we can add an edge with weight = 1 from T1 to T2.
• Once the graph has been built, the minimum number of operations from 1 to N, would be the shortest distance from 1 to N in the graph.

However, since the number can be increased using the first operation, we need an upper bound to know when to stop building the graph.

• Suppose, an integer T consists of D digits. Using the second operation does not change the number of digits, and using the first operation either increases or keeps D the same.
• So now we know that the number of digits is non-decreasing. Hence, we don’t need to use any number with more digits than N, we can use 10*N as the upper limit.

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

• Объявите массив расстояний dis[10*N] , чтобы найти расстояние или минимальную стоимость преобразования 1 в N .
• Назначьте все dis[i] INF (большое значение)
• Запустите BFS с узла 1. В BFS:
  • Если node = N , значит, мы достигли цели. Так сломай этот звонок.
  • Если node*X < 10*N , поместите node*X в очередь для дальнейшего использования в вызове BFS.
  • Если узел не делится на 10 и узел>10 и right_shuffle(узел)<10*N
    • Поместите right_shuffle (узел) в очередь
• Если достижение N (т.е. dis[N] = inf ) невозможно, вернуть -1.

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

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