Given an integer n, you must transform it into 0 using the following operations any number of times:

Change the rightmost (0th) bit in the binary representation of n.
Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0.

Return the minimum number of operations to transform n into 0.
 
Example 1:
Input: n = 0
Output: 0

Example 2:
Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".
"11" -> "01" with the 2nd operation since the 0th bit is 1.
"01" -> "00" with the 1st operation.

Example 3:
Input: n = 6
Output: 4
Explanation: The binary representation of 6 is "110".
"110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0.
"010" -> "011" with the 1st operation.
"011" -> "001" with the 2nd operation since the 0th bit is 1.
"001" -> "000" with the 1st operation.

Example 4:
Input: n = 9
Output: 14

Example 5:
Input: n = 333
Output: 393

 
Constraints:

0 <= n <= 109

Difficulty: interview

Starter code:

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        

Solutions:
class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        s = 0
        m = n
        while m:
            s += m & 1
            m >>= 1

        k = 1
        while s:
            s -= bool(n & k)
            n ^= (s & 1) and k
            k <<= 1

        return n

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        ans = 0
        while n:
            ans^=n
            n//=2
        
        return ans


class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n <= 1: return n
        b = int(math.log2(n)) + 1        
        return ((1 << b)-1) - self.minimumOneBitOperations(n - (1 << (b-1)))        

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        result = 0
        while n:
            result = ((n & -n) << 1) - 1 - result
            n -= n & -n
        return result

from functools import lru_cache

# removehigh = [(1 << l) - 1 for l in range(31)]
@lru_cache()
def removehigh(l: int) -> int:
    if l <= 1:
        return l + 1
    return (1 << l)
    
@lru_cache()
def sethigh(l: int, n: int) -> int:
    if n == 0:
        return removehigh(l) - 1
    
    t2 = 1 << l - 2
    
    if n >= t2:
        return removehigh(l - 1) + remove(n - t2)
    
    if n & (n - 1) == 0:
        return removehigh(l) - removehigh(n.bit_length())
    
    return removehigh(l - 1) + sethigh(l - 1, n) 

    
@lru_cache()
def remove(n: int) -> int:
    if n <= 1:
        return n
    elif n <= 3:
        return 5 - n
    
    l = n.bit_length()
    if n & (n - 1) == 0:
        return removehigh(l) - 1
    
    t3 = 3 << l - 2
    if n >= t3:
        return removehigh(l - 1) + remove(n - t3)
    
    t1 = 1 << l - 1
    return removehigh(l - 1) + sethigh(l - 1, n - t1) 



class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        return remove(n)


class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        
        ans = 0
        
        while n>0:
            ans = ans^n
        
            n = n>>1
        
        return ans

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        
        if n == 0:
            return 0
        if n == 1:
            return 1
        
        tot = 0
        
        b = bin(n)[2:]
        if b[1] == '0':
            tot += 2**(len(b)-2)
            
        lastChanged = b[1] == '0'
        for i in range(2,len(b)):
            if (lastChanged and b[i] == '0') or (not lastChanged and b[i] == '1'):
                tot += 2**(len(b)-1-i)
                lastChanged = True
            else:
                lastChanged = False
        
        return tot + 1 + self.minimumOneBitOperations(int('1' + '0'*(len(b)-2),2))


from functools import lru_cache

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        return self.toZero(n)
    
    @lru_cache(maxsize=None)
    def toZero(self, n):
        if n <= 1:
            return n
        elif n == 2:
            return 3
        elif n == 3:
            return 2
        
        offset = 0
        while ((1 << (offset + 1)) - 1) & n != n:
            offset += 1
        
        target = 1 << (offset - 1)
        return self.topower2(n & ((target << 1) - 1), target) + 1 + self.toZero(target)
    
    @lru_cache(maxsize=None)
    def topower2(self, n, target):
        if n == 0:
            return 1 + self.topower2(1, target)
        elif n == target:
            return 0
        
        offset = 0
        while ((1 << (offset + 1)) - 1) & n != n:
            offset += 1
             
        if n & target == 0:
            return self.topower2(n, target >> 1) + 1 + self.toZero(target >> 1)
        
        return self.toZero(n & (target - 1))