Problem Statement:
You have a broken calculator and there is a number showing on the display.
You can perform below two operations:
Double: Multiply the number by 2
Decrement: Subtract the number by 1.
Initially calculator is displaying number ‘x’ and you are given a number ‘y’.
Return the minimum number of operations needed to display the number ‘y’
Example
x = 2 y = 3
Operations = 2
Double the number and decrement the number. It will take 2 operations to move the number from 2 to 3.
Solution
So at first you can think that we double the ‘x’ till it is greater than ‘y’ and then start decrementing it.
But this is not a efficient solution.
The efficient solution will be, instead of making ‘x’ move to ‘y’, we make ‘y’ to ‘x’.
If ‘y’ is odd, we first add a number and then divide it.
If ‘y’ is even we perform division operation and then do the addition operation.
So when y <= x, we stop the division and then increase y til it reaches x.
If y > x, then we keep dividing ‘y’ till it is smaller than ‘x’
Solution in C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
int broken_calculator(int X, int Y)
{
int res = 0;
while (Y > X)
{
Y = Y % 2 > 0 ? Y + 1 : Y / 2;
res++;
}
return res + X - Y;
}
int main()
{
int x = 2;
int y = 3;
cout<<"The min operations to change "<< x << " to "<<y <<" is = " << broken_calculator(x, y)<<endl;
return 0;
}
Output:
The min operations to change 2 to 3 is = 2