Greedy: Perform operations on a broker calculator

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
Write a Comment

Leave a Comment

Your email address will not be published. Required fields are marked *