991. Broken Calculator

發表於 | 分類於

problem

solution

  • iterative

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution {
    public:
        int brokenCalc(int startValue, int target) {
            int ret= 0;
            while(target > startValue){
                target = (target%2==0)?target/2:target+1;
                ret++;
            }
            return ret+startValue-target;
        }
    };

  • recursive

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    class Solution {
    public:
        int brokenCalc(int startValue, int target) {
            if(startValue==target ) return 0;
            if(startValue > target) return startValue-target;
            if( target%2==1) return 1+brokenCalc(startValue, target+1);
            else return 1+brokenCalc(startValue, target/2);
            
        }
    };

    analysis

  • time complexity O(logn)

  • space complexity O(1)