[greed] leetcode991 Broken Calculator

991. Broken Calculator

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can:

multiply the number on display by 2, or
subtract 1 from the number on display.
Given two integers startValue and target, return the minimum number of operations needed to display target on the calculator.

The question ：x You can multiply by 2 Operation and reduction 1 operation , seek x Turn into y The minimum number of operations

Ideas ： greedy

Can be reversed ：y You can add 1 operation , Or divide by 2 The operation of （y If it's even ）

Can prove that ： When y If it's even , Divide 2 The number of operations obtained must be greater than 1 The number of operations is small

 

therefore , When y In the case of odd numbers ,y Can only add 1; When y If it's even ,y Can only be divided by 2

When y Less than x when , Add only 1 operation .

Time complexity O（logY）

class Solution {
    public int brokenCalc(int x, int y) {
        int res=0;
        while(y>x){
            if(y%2==1){
               y++;
            }else{
                y/=2;
            }
            res++;
        }
        return res+x-y;
   } 
}