題目敘述
There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:
- multiply the number on display by
2, or
- subtract
1 from the number on display.
Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.
Example 1:
Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.
Example 2:
Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.
Example 3:
Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.
Constraints:
題目翻譯
題目提供兩個參數 startValue 和 target。從參數 startValue 開始，只能做兩種操作"減一"和"乘2"，找出最少需要操作幾次次數是可以變成 target。
解法解析
這題的解法是採用反向的概念，從 target 改成"加 1"和"除 2"。一開始如果是偶數的話就採用 target /2，可以盡快的縮小值。如果是奇數的話就 target - 1，將其變成偶數。等到 startValue >= target 的時候，就可以將之前的操作次數 ans 跟 startValue - target 相加。因為 tartget 跟 startValue 之間的差距可以用多個 +1 的操作補齊，所以直接 startValue - target 即可。
startValue = 3, target = 14
1. target = 14 is even => target / 2 => 7, ans = 1
2. target = 7 is odd => target - 1 = 6, ans = 2
3. target = 6 is even => target / 2 = 3, ans = 3
4. startValue >= target => 3(ans) + 3(startValue) - 3(target) => 3
解法範例
Go
func brokenCalc(startValue int, target int) int {
var ans int
for target > startValue {
ans++
if target%2 == 1 {
target++
} else {
target /= 2
}
}
return ans + startValue - target
}
JavaScript
var brokenCalc = function (startValue, target) {
let ans = 0;
while (target > startValue) {
ans++;
if (target % 2) {
target++;
} else {
target /= 2;
}
}
return ans + startValue - target;
};
Kotlin
class Solution {
fun brokenCalc(startValue: Int, target: Int): Int {
var ans = 0
var diff = target
while (diff > startValue) {
ans++
if (diff % 2 == 1) {
diff++
} else {
diff /= 2
}
}
return ans + startValue - diff
}
}
PHP
class Solution
{
function brokenCalc($startValue, $target)
{
$ans = 0;
while ($target > $startValue) {
$ans++;
if ($target % 2) {
$target++;
} else {
$target /= 2;
}
}
return $ans + $startValue - $target;
}
}
Python
class Solution:
def brokenCalc(self, startValue: int, target: int) -> int:
ans = 0
while target > startValue:
ans += 1
if target % 2:
target += 1
else:
target = int(target / 2)
return ans + startValue - target
Rust
impl Solution {
pub fn broken_calc(start_value: i32, target: i32) -> i32 {
let mut ans = 0;
let mut diff = target;
while diff > start_value {
ans += 1;
if diff & 1 == 1 {
diff += 1;
} else {
diff /= 2;
}
}
ans + start_value - diff
}
}
Swift
class Solution {
func brokenCalc(_ startValue: Int, _ target: Int) -> Int {
var ans = 0
var diff = target
while diff > startValue {
ans += 1
if diff % 2 == 1 {
diff += 1
} else {
diff /= 2
}
}
return ans + startValue - diff
}
}