Problem statement

https://leetcode.com/problems/integer-replacement/

Solution

First solution is to notice that if number is even, that we always need to divide it by 2. If number is even, like 21, we have two optoins: to make it 10 or 11 in two steps. Notice that one of these two options will always be even and another odd, so if we have options 2x, 2x + 1 on some step, on the next steps we have options x, x+1, that is again no more than two options, which leads to good complexity.

Complexity

It is O(log n) for time, because on each level we have no more than 2 options and O(log n) for space due to recursion stack.

Code

class Solution:
    def integerReplacement(self, n):
        @lru_cache(None)
        def dp(x):
            if x == 1: return 0
            if x % 2 == 0: return dp(x//2) + 1
            return min(dp((x+1)//2), dp((x-1)//2)) + 2
        
        return dp(n)

Remark

We can also use the following observation: if we have number 4n+3, n>0, in two steps we can either achieve 2n+1 or 2n+2 and it can be shown that 2n+2 is better: it includes all solutions which 2n+1 have. Also if we have 4n + 1, and we have choice 2n and 2n+1, we always need to choose 2n. Overall time complexity is O(log n), because each two iterations number decrease at least twice and space complexity is O(1).