[LeetCode][991. Broken Calculator] Greedy: Reverse Thinking with Binary Algorithm

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

By Long Luo

This article is the solution Greedy: Reverse Thinking with Binary Algorithm of Problem 991. Broken Calculator.

Intuition

  1. If startValue>target\textit{startValue} \gt \textit{target}, so return startValue>target\textit{startValue} \gt \textit{target};
  2. Considering such cases: 2→32 \to 3, 2→52 \to 5, 1→1281 \to 128, 1→1001 \to 100;
  3. startValue=startValue×2i\textit{startValue} = \textit{startValue} \times 2^i, when startValue\textit{startValue} grows bigger, the last startValue\textit{startValue} is closer to target/2\textit{target} / 2 that we only need double startValue\textit{startValue} once.

So think reversly:

  1. if target is even, the minimum operand is convert startValuestartValue equal to target/2+1\textit{target} / 2 + 1;
  2. if target is odd, the minimum operand is convert startValuestartValue equal to (target+1)/2+2(\textit{target} + 1) / 2 + 2.

Let’s coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int brokenCalc(int startValue, int target) {
    if (startValue >= target) {
        return startValue - target;
    }

    int ans = 0;
    while (startValue < target) {
        if (target % 2 == 0) {
            target >>= 1;
            ans++;
        } else {
            target = (target + 1) >> 1;
            ans += 2;
        }
    }

    return ans + startValue - target;   
}

Analysis

  • Time Complexity: O(logn)O(logn).
  • Space Complexity: O(1)O(1).

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗