By Long Luo

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

Intuition

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

So think reversly:

1. if target is even, the minimum operand is convert \(startValue\) equal to \(\textit{target} / 2 + 1\);
2. if target is odd, the minimum operand is convert \(startValue\) equal to \((\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)\).
• Space Complexity: \(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. 😉😃💗