Broken Calculator

Easy
0/40
Average time to solve is 20m
1 upvote
Asked in companies
ArcesiumDisney + HotstarExpedia Group

Problem statement

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’

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
2
8 4
3 10
Sample Output 1:
4
3
Explanation for Sample Input 1:
In test case 1: 

In the first operation, we convert 8 to 7 ( 8 - 1 = 7 )
In the second operation, we convert 7 to 6 ( 7 - 1 = 6 )
In the third operation, we convert 6 to 5 ( 6 - 1 = 5 )
In the fourth operation, we convert 5 to 4 ( 5 - 1 = 4 )

Thus a minimum of 4 operations is required for conversion.

In test case 2:
In the first operation, we convert 3 to 6  ( 3*2 = 6 )
In the second operation, we convert 6 to 5 ( 6 - 1 = 5 )
In the third operation, we convert 5 to 10 ( 5*2 = 10 )

Thus a minimum of 3 operations is required for conversion.
Sample Input 2:
3
6 17
19 25
12 19
Sample Output 2:
5
8
4
Hint

We can check every possibility but constraints are high can we store the previously occurred subproblem?

Approaches (2)
Recursion

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.

Time Complexity

O(Y), where ‘Y’ is given in the problem.

 

In the worst case, the recursion will work for all values of ‘X’ <= ‘Y’, thus O(Y).

Space Complexity

O(Y), where ‘Y’ is given in the problem.

 

We are creating a DP of size ‘Y’+1 thus space complexity is O(Y)

Code Solution
(100% EXP penalty)
Broken Calculator
Full screen
Console