Last Updated: 8 Apr, 2021
Broken Calculator
Easy
Asked in companies
You are given two integers ‘X’ and ‘Y’. You can convert the number ‘X’ into another integer ‘Y’ using the following two operations in any order.
i) Multiply ‘X’ by 2
ii) Subtract 1 from ‘X’
Your task is to find the minimum number of operations needed to convert ‘X’ into ‘Y’.
Note: It is always possible to convert ‘X’ into ‘Y’
Input Format:
The first line of the input contains ‘T’ denoting the number of test cases.
The first line of each test case contains the two integers ‘X’ and ‘Y’.
Output Format:
For each test case, print a single line containing a single integer denoting the minimum number of operations needed.
The output of each test case will be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 20
0 <= X, Y <= 10 ^ 5
Where ‘T’ denotes the number of test cases
Time Limit: 1 sec.
Approaches
Explanation:
- The simple idea is to recursively solve the problem while memoizing (DP).
- DP[ i ] represents the minimum number of moves to convert ‘i’ into ‘Y’.
- In every step, you will convert X into 2 * X and X into X - 1 at the cost of 1 operation.
- If you have arrived at some ‘X’ before i.e. you have already calculated the answer for it. Then simply return it.
- If ‘X’ >= ‘Y’, the answer is ‘X’ - ‘Y’ because it is always optimal to keep decreasing ‘X’ until we get ‘Y’, there is no point in increasing ‘X’ by multiplying it by 2.
Algorithm:
- Create a DP array of size Y+1, because that is the maximum value ‘X’ can achieve.
- Set DP[ i ] = -1 for 0 <= i <= Y, to represent ‘i’ hasn’t been visited in the recursion.
- Then calculate the answer recursively, using function ‘minSteps()’, where
- If ‘X’ < 0 then return ‘INF’, i.e. ‘Y’ cannot be reached.
- If ‘X’ >= ‘Y’ return ‘X’ - ‘Y’
- Check if ‘X’ is already visited, i.e. if DP[X] != -1 then return DP[X], which we have already calculated.
- Set DP[X] = ‘INF’, to just mark that we have visited ‘X’, here ‘INF’ is used so that if in future recursion we were to encounter ‘X’ in further recursion then it won’t go into a recursive loop.
- Calculate DP[X] using recursive call for ‘minSteps()’
- DP[x] = 1 + min( minSteps(X * 2, Y) , minSteps(X - 1, Y) );
- Print the value calculated by this original recursive function.
Note: ‘INF’ represents INFINITY which is a large value that cannot possible by the answer.
Explanation:
- Here we look at this problem from a different perspective, rather than doing operations to ‘X’ it is always better to do opposite operations in ‘Y’. i.e. if X * 2 = Y, then Y / 2 = X, similarly if X - 1 = Y, then Y + 1 = X, so we can invert the operations and do them ‘Y’ and our answer won’t change.
- So if ‘X’ < ‘Y’ then we can do operations on ‘Y’, the benefit of this is that we know when to do what operations on ‘Y’, because division by 2 is only possible when the number is, even so, whenever ‘Y’ is even we divide it by 2 ( because that is the only way to decrease ‘Y’).
- Else if ‘Y’ is odd, then we make it even by adding 1 to it.
- If ‘X’ >= ‘Y’, the answer is ‘X’ - ‘Y’ because it is always optimal to keep decreasing ‘X’ until we get ‘Y’, there is no point in increasing ‘X’ by multiplying it by 2.
Algorithm:
- Create a variable names ‘Res’ = 0.
- Do the following till ‘Y’ > ‘X’:
- If ‘Y’ is even then divide it by 2
- Else if it is odd then increment it by 1
- Increment ‘Res’, as we have done one operation.
- If ‘X’ > ‘Y’, increment ‘Res’ by ‘X’ - ’Y’, i.e. ‘Res’ = ‘Res’ + ’X’ - ‘Y’
- Return ‘res’ at the end.