# leetcode 1611. Minimum One Bit Operations to Make Integers Zero（python）

2022-02-01 09:06:40

「 This is my participation 11 The fourth of the yuegengwen challenge 25 God , Check out the activity details ：2021 One last more challenge

### describe

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
Copy code ``````

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.
Copy code ``````

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.
Copy code ``````

Example 4:

``````Input: n = 9
Output: 14
Copy code ``````

Example 5:

``````Input: n = 333
Output: 393
Copy code ``````

Note:

``````0 <= n <= 109
Copy code ``````

### analysis

According to the meaning , Given an integer n, It must be converted to... Using any number of the following operations 0：

• change n The binary of represents the rightmost bit . Sure 0 Turn into 1 , It's fine too 1 Turn into 0 .
• If the first (i-1) Bit is set to 1 And No (i-2) To the first 0 Bit is set to 0, Then change n In the binary representation of i position . Sure 0 Turn into 1 , It's fine too 1 Turn into 0 .

Note that the index of binary bits in the title is from right to left , Return to n Convert to 0 Minimum operands of . Because method one just puts the rightmost 0 and 1 swap , Cannot operate on previous characters , So the key is to skillfully use method 2 to change , If we give an example , take 101011 Turn into 000000 , The simplest idea is recursion ：

• （1）101011 The first is 1 , Want to turn it into 100000 , Just call the custom convert function , The function of this function is to find out that 01011 Turn into 10000 The minimum number of times
• （2） Application method 2 will change the 110000 Turn into 010000 the 1 operations , Then the calculation will 10000 Turn into 00000 The number of times , The same method as above , take 0000 adopt convert The function becomes 1000 , Doing the same thing , Until it finally becomes 000000
• （3） So define recursive functions dfs , Indicates the minimum number of operations on the input binary , To express the above process is dfs(101011) = convert(01011) + 1 + dfs(10000)

however convert There are two situations ：

• The first case is that the first number of binary is 1 , Such as 1110 . Then call directly dfs(110) that will do
• The second case is that the first number of binary is 0 , Such as 0111 , Recursion is needed again ：convert(0111) = convert(111) + 1 + dfs(100)

``````class Solution(object):

def __init__(self):
self.d = {}
self.t = {}

def minimumOneBitOperations(self, n):
"""
:type n: int
:rtype: int
"""
return(self.dfs(bin(n)[2:]))

def dfs(self, s):
if s == '0' : return 0
if s == '1' : return 1
if s in self.d : return self.d[s]
if  s[0] == '0': return self.dfs(s[1:])
m = s[1:]
n = list(s[1:])
n[0] = '1'
for i in range(1, len(n)):
n[i] = '0'
n = ''.join(n)
self.d[s] = self.convert(m) + 1 + self.dfs(n)
return self.d[s]

def convert(self, s):
if s == '0' : return 1
if s == '1' : return 0
if s in self.t : return self.t[s]
if s[0] == '1':
self.t[s] = self.dfs(s[1:])
else:
m = s[1:]
n = list(s[1:])
n[0] = '1'
for i in range(1, len(n)):
n[i] = '0'
n = ''.join(n)
self.t[s] = self.convert(m) + 1 + self.dfs(n)
return self.t[s]

Copy code ``````

### Running results

``````Runtime: 44 ms, faster than 5.17% of Python online submissions for Minimum One Bit Operations to Make Integers Zero.
Memory Usage: 13.3 MB, less than 77.59% of Python online submissions for Minimum One Bit Operations to Make Integers Zero.
Copy code ``````