Problem statement

https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero/

Solution

For each number, let us look at the last bit, e.g in number 10100111000100, we look at 2-nd place from the end (starting with zero index), then what we can do is two options:

  1. Move this one to the right, we need 4 operations in this case in general case 2^i. Actually if we started to move to the rigth, we continue until we remove this one at all and we need 2^{i+1} - 1 operations for this.
  2. Move this one to the left, we need 8 operations in this case, in general case 2^(i+1).

Also we need to deal with cases whan we can not move to the right, like ....110000, then we can either move to the left or remove one so we have ....010000.

Complexity

I think it is O(log n), however I do not have strict proof: intuition, that if in the beginning we have number with k ones, than on each next level we have no more than two numbers with k-1, k-2, …, 1 ones.

Code

class Solution:
    def minimumOneBitOperations(self, n):
        @lru_cache(None)
        def dp(n):
            if n == 0: return 0
            if n & (n-1) == 0: return 2*n - 1
            p = n - (n & (n-1))
            if (2*p) & n == (2*p):
                return min(dp(n-2*p) + 1, dp(n-p) + 2*p-1)
            return min(dp(n-p) + 2*p-1, dp(n+p) + p*2)
        
        return dp(n)

Solution 2

Actually, there is better solution.

Lemma: shortest path from 10..00 to 00..00 where we have n zeros has length 2^(n+1) - 1.

Then imagine, that we have number 101101000, and we want to get 000000000. We can split path as following:

000000000 … 101101000 … 100000000

We know that whole path has length 2^(n+1) - 1, then to find answer to our question we need to subtract from 2^(n+1) - 1 the length of path from 101101000 to 100000000: if we have 3 pointes (A, B, C) and we know that path from A to C go through B and we know shortest path from A to B and from A to C, than we know it from B to C.

Complexity

It is O(log n) for time and space.

Code

class Solution:
    def minimumOneBitOperations(self, n):
        @lru_cache(None)
        def dp(n):
            if n == 0: return 0
            b = int(log2(n))
            return (1<<(b + 1)) - 1 - dp(n - (1<<b))
        
        return dp(n)

Remark

Actually, what we have in this problem is called Gray code, see https://oeis.org/A006068.