Минимизируйте шаги, чтобы преобразовать N в степень 2, удалив или добавив любую цифру

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

• Удалите любую одну цифру d из числа.
• Добавьте любую цифру d в конце числа N .

Примеры:

Input: N = 1092
Output: 2
Explanation:
Following are the steps followed:

1. Removing digit 9 from the number N(= 1092) modifies it to 102.
2. Adding digit 4 to the end of number N(= 102) modifies it to 1024.

After the above operations, the number N is converted into perfect power of 2 and the number of moves required is 2, which is the minimum. Therefore, print 2.

Input: N = 4444
Output: 3

Подход: данная проблема может быть решена с использованием жадного подхода, идея состоит в том, чтобы сохранить все числа, которые являются степенью 2 и меньше 10 ²⁰ , и проверить с каждым числом минимальные шаги для преобразования данного числа в степень 2. Для решения проблемы выполните следующие действия:

• Инициализируйте массив и сохраните все числа, которые являются степенью 2 и меньше 10 ²⁰ .
• Инициализируйте переменную ответа как длина + 1 как максимальное необходимое количество шагов.
• Перебрать диапазон [0, len), где len — длина массива с использованием переменной x , и выполнить следующие шаги:
  • Инициализируйте переменную, скажем, position как 0 .
  • Перебрать диапазон [0, len), где len — длина числа с использованием переменной i , и если позиция меньше, чем len(x) , а x[position] равно num[i] , то увеличьте значение позицию на 1 .
  • Обновите значение best как минимальное значение best или len(x) + len(num) – 2*position .
• После выполнения вышеуказанных шагов выведите в качестве результата значение best .

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

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