Сложность: medium
Имеется неисправный калькулятор, на экране которого изначально отображается целое число startValue. За одну операцию можно:
Умножить число на экране на 2, или
Вычесть 1 из числа на экране.
Даны два целых числа startValue и target. Верните минимальное количество операций, необходимых для отображения target на калькуляторе.
Пример:
Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
👨💻 Алгоритм:
1⃣Обратный путь:
Если target больше startValue, то попытайтесь уменьшить target, чтобы привести его к startValue.
Если target четный, разделите его на 2, иначе прибавьте 1.
2⃣Подсчет операций:
Повторяйте шаги, пока target не станет меньше или равен startValue.
После этого вычитайте из startValue оставшееся значение target.
3⃣Возврат результата:
Возвращайте суммарное количество выполненных операций.
😎 Решение:
class Solution:
def brokenCalc(self, startValue: int, target: int) -> int:
operations = 0
while target > startValue:
operations += 1
if target % 2 == 0:
target //= 2
else:
target += 1
return operations + (startValue - target)
Ставь 👍 и забирай 📚 Базу знаний