991. Broken Calculator

題目敘述

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:

• 1 <= x, y <= 10**9

題目翻譯

題目提供兩個參數 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

/**
 * @param {number} startValue
 * @param {number} target
 * @return {number}
 */
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
{

    /**
     * @param Integer $startValue
     * @param Integer $target
     * @return Integer
     */
    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
    }
}