BinarySearch 0922 Manipulate Bits to Zero

Problem statement

https://binarysearch.com/problems/Manipulate-Bits-to-Zero/

Solution

Equal to Leetcode 1611. Minimum One Bit Operations to Make Integers Zero.

Complexity

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

Code

class Solution:
    def solve(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)