991. Broken Calculator

main idea: if Y is odd, the last number to be reached before Y is Y+1 (optimal path); if Y is even, the last number to be reached before Y is Y//2 (optimal path)

recursive relation: if(x>=y): cost(x,y) = x - y; if(x<y): cost(x,y) = 1+ cost(x,y+1) if y odd else 1+cost(x,y//2)

class Solution:
    def brokenCalc(self, X: int, Y: int) -> int:
        cnt = 0
        while Y > X:
            if Y%2: # Y is odd 
                Y += 1 
            else: # Y is even 
                Y = Y//2
            cnt += 1 
        return cnt + X-Y