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