1611. Minimum One Bit Operations to Make Integers Zero

Problem Link

Description

---

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 = 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 2:

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.

 

Constraints:

• 0 <= n <= 109

Solution

---

Python3

class Solution:
    @cache
    def minimumOneBitOperations(self, n: int) -> int:
        # 1 0
        # 10 11 01 00
        # 100 101 111 110 010 011 001 000
        # number of operations = 2^(k+1) - 1
 
        # 0 -> 1000 = 15 operations
        # 1000 1001 1011 1010 1110 (4 operations)
        
        # b = 1000
        # n = 1xxx
        # n' = 0xxx
        # 0 = 0000
 
        # Moves[b->0] = 2^4-1
        # Let Moves[n'->0] = f(n').
        # Let Moves[b->n] = A. Then, A == f(n'). (Because of the symmetry. 000->xxx is same as xxx->000)
        # Let Moves[n->0] = f(n)
        # Therefore, the recursion relation is
        # f(b) = 2^4-1 = Moves[b->n] + Moves[n->0]
        # = A + f(n)
        # = f(n') + f(n)
 
        if n == 0: return 0
        k = int(log2(n))
 
        return ((1 << (k + 1)) - 1) - self.minimumOneBitOperations(n - (1 << k))