Today's challenge on Leetcode in based on a Maths/ Greedy Problem. It is a medium level problem and sounds easy but may leave you scratching your head in terms of an optimal solution.

991. Broken Calculator

Problem Statement

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

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

Thought Process:

The immediate thought striking your mind would be to increase the startValue using * operator (in case of a smaller startValue) or decrease it by subtracting to make it equal to target and count the steps we took in our journey.

It can lead to errors so the desired method is to do the otherwise backward approach. To reduce the target using the exact opposite operators of division and subtraction to count the occurrences of operations.

In case, target becomes lesser than startValue, we will increment until the startValue and return the difference along with the actual counter. Confused about this step, proceed further and understand.

Logic

1. The approach is simple, we declare a counter and run a loop which is terminated once our target value is no more greater than the startValue.

2. In case our target is odd, we increment the value of target by 1 else we will divide the target value into half.

3. Eventually, once the loop is terminated, we will return the summation count of times the loop ran and the difference between the startValue and target.

4. Difference between startValue and target will be decremented on other side of startValue to make it equal to the target along with the counter that ran along the loop.

Code

In case, you are looking to learn practice Python from scratch or want to practice DSA then do checkout my YouTube Channel for free lectures and code-along sessions!
Code Broski: Click here to redirect to Python Fundamentals playlist!