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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Bit manipulation

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

@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)