Минимизируйте шаги, необходимые для преобразования числа N в M с помощью арифметических операторов.

Даны два целых числа N и M , задача состоит в том, чтобы найти последовательность минимального количества операций, необходимых для преобразования числа N в M , так что в каждой операции N можно добавить (N = N + N) , вычесть как (N = N – N) , умноженный как (N = N*N) или разделенный как (N = N/N) . Если невозможно преобразовать N в M , выведите «-1» .

Примеры:

Input: N = 7, M = 392
Output: 3 
+, *, +
Explanation:
Following are the operations performed:

1. Performing addition modifies the value of N as 7 + 7 = 14.
2. Performing multiplication modifies the value of N as 14*14 = 196.
3. Performing addition modifies the value of N as 196 + 196 = 392.

After the above sequence of moves as “+*+”, the value of N can be modified to M.

Input: N = 7, M = 9
Output: -1
Explanation: There are no possible sequence of operations to convert N to M.

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

• Операция вычитания всегда дает 0, поскольку N = N – N = 0. Точно так же операция деления всегда дает 1, поскольку N = N / N = 1. Таким образом, эти случаи можно легко обработать.
• Для сложения и умножения проблема может быть решена с помощью обхода в ширину путем создания состояния для каждой из последовательностей операций в возрастающем порядке количества операций.

Шаги для решения данной проблемы следующие:

• Поддерживайте очередь для хранения состояний BFS, где каждое состояние содержит текущее достижимое целое число N' и строку, представляющую последовательность операций для достижения N' из N .
• Сначала добавьте в очередь состояние {N, ""}, представляющее N , и последовательность операций как пустую.
• Также добавьте в очередь состояние {1, «/»} для операции деления.
• Во время обхода в ширину для каждого состояния добавьте два состояния, где 1-е состояние будет представлять сложение (N' + N'), а 2-е состояние будет представлять умножение (N' * N') .
• Поддерживайте неупорядоченную карту, чтобы проверить, посещалось ли уже текущее состояние во время обхода BFS.
• Если значение текущего состояния равно M , то результатом является последовательность операций, полученная до M. В противном случае выведите «-1» .

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

Временная сложность: O (мин (2 ^{log ₂ (M – N)} , M – N))
Вспомогательное пространство: O((MN)* log ₂ (M – N))