Skip to content

LeetCode: 991-Broken Calculator 解題紀錄

Last Updated on 2022-03-23 by Clay

題目

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 <= 109

我們有一個起始值 startValue 以及一個目標值 target,而我們能做的操作只有將 startValue x2 或是 -1 —— 最終要讓 startValue 等於 target,而我們要回傳需要操作的最少步驟。


解題思路

Greedy 解法

這題比較取巧的是,如果想要使用貪婪解法,我們必須將目標值 target 視為起點,反向操作去逼近起始值 startValue

這是因為如果我們真的拿起起始值去操作、以逼近目標值 target,可能會存在著『先減去部分值再乘以二』比『直接乘以二再減去差值』操作步驟更少的情況(反過來的情況也是有的);這樣一來,我們就得不斷地同時評估兩種操作的可能性。

但若是使用 target 逼近 startValue,操作就變得單純:

  • 如果 target 小於 startValue:回傳當前累積操作次數 + startValue - target(因為兩者的差需要不斷 +1 的操作)
  • 如果 target 是偶數:直接除以 2
  • 如果 target 是奇數:先加 1 使其變成偶數

因為最快的逼近方法就是除以 2,所以最快的逼近方法,自然就是在每次可以除以 2 時進行此操作,故為貪婪解。


Greedy 解法複雜度

因為只需要儲存操作次數,故空間複雜度為 O(1);而我看到大部分此解法的時間複雜度都寫 O(log(n)),我想是可以視為大部分的逼近都是靠除 2 來達成的。

Time complexityO(log n)
Space complexityO(1)


Greedy 解法 C++ 範例程式碼

class Solution {
public:
    int brokenCalc(int startValue, int target) {        
        // Init
        int opt = 0;
        
        while (startValue < target) {
            if (target % 2 == 1) {
                ++target;
            }
            else {
                target /= 2;
            }
            
            // Step
            ++opt;
        }
        
        return opt + startValue - target;
    }
};



Greedy 解法 Python 範例程式碼

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        # Init
        opt = 0
        
        # Operatings
        while startValue < target:
            if target % 2 == 1:
                target = target + 1
            else:
                target = target // 2
            
            # Step
            opt += 1
            
        # Return opt + distance
        return opt + startValue - target
            

References


Read More

Leave a Reply