Сложность: 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⃣Возврат результата:
Возвращайте суммарное количество выполненных операций.
😎 Решение:
public class Solution {
public int brokenCalc(int startValue, int target) {
int operations = 0;
while (target > startValue) {
operations++;
if (target % 2 == 0) {
target /= 2;
} else {
target += 1;
}
}
return operations + (startValue - target);
}
}Ставь 👍 и забирай 📚 Базу знаний