Problem

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 displaytarget on the calculator.

Examples

Example 1

1
2
3

Input: startValue = 2, target = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2

1
2
3

Input: startValue = 5, target = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3

1
2
3

Input: startValue = 3, target = 10
Output: 3
Explanation: Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Constraints

  • 1 <= startValue, target <= 10^9

Solution

Method 1: Greedy Reverse Approach (Optimal)

Intuition

Instead of moving from startValue to target, work backwards from target to startValue. If target is even, divide by 2 (reverse of multiply by 2). If odd, increment by 1 (reverse of subtract 1). This minimizes the number of operations.

Approach

  • While target is greater than startValue:
    • If target is even, divide by 2.
    • If odd, increment by 1.
  • When target <= startValue, the only way is to subtract 1 repeatedly.
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution:
    def brokenCalc(self, startValue: int, target: int) -> int:
        ops = 0
        while target > startValue:
            if target % 2 == 0:
                target //= 2
            else:
                target += 1
            ops += 1
        return ops + (startValue - target)
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int brokenCalc(int startValue, int target) {
        int ops = 0;
        while (target > startValue) {
            if (target % 2 == 0) {
                target /= 2;
            } else {
                target++;
            }
            ops++;
        }
        return ops + (startValue - target);
    }
}
C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
public:
    int brokenCalc(int startValue, int target) {
        int ops = 0;
        while (target > startValue) {
            if (target % 2 == 0) target /= 2;
            else target++;
            ops++;
        }
        return ops + (startValue - target);
    }
};
Go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func brokenCalc(startValue int, target int) int {
    ops := 0
    for target > startValue {
        if target%2 == 0 {
            target /= 2
        } else {
            target++
        }
        ops++
    }
    return ops + (startValue - target)
}
Kotlin
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    fun brokenCalc(startValue: Int, target: Int): Int {
        var t = target
        var ops = 0
        while (t > startValue) {
            if (t % 2 == 0) t /= 2 else t++
            ops++
        }
        return ops + (startValue - t)
    }
}
Rust
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

impl Solution {
    pub fn broken_calc(start_value: i32, mut target: i32) -> i32 {
        let mut ops = 0;
        while target > start_value {
            if target % 2 == 0 {
                target /= 2;
            } else {
                target += 1;
            }
            ops += 1;
        }
        ops + (start_value - target)
    }
}

Complexity

  • ⏰ Time complexity: O(log(target))
  • 🧺 Space complexity: O(1)