Минимизируйте ходы, чтобы уменьшить N до 0, используя заданные операции

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

• Увеличьте или уменьшите значение N на 1.
• Умножьте значение N на -1.
• Разделите значение N на 2, если N четно.
• Уменьшите значение N до √N, если N — полный квадрат.

Пример:

Input: N = 50
Output: 6
Explanation: The moves performed are: 50 (/2) -> 25 (√) -> 5 (- 1) -> 4 (/2) -> 2 (-1) -> 1 (-1) -> 0. Therefore, the required number of moves is 6 which is the minimum possible.

Input: N = 75
Output: 8

Подход: Данную задачу можно эффективно решить с помощью динамического программирования. Идея состоит в том, чтобы использовать хеширование и поиск в ширину для 0 до тех пор, пока не будет достигнуто N. Хеширование используется для того, чтобы один и тот же номер не посещался дважды. Для решения проблемы можно выполнить следующие шаги:

• Используйте BFS, добавляя все возможные числа, до которых можно добраться из 0, в очередь, а также в хэш-карту, чтобы они не посещались снова
• Возвращает количество ходов, рассчитанное после достижения N .

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

Временная сложность: O (log N)
Вспомогательное пространство: O (K * log N), где K — возможные разрешенные операции.