1611. Minimum Number of One Bit Operations to Make Integers Zero - Explanation

1. Math (Recursion)

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        if n == 0:
            return 0

        k = 1
        while (k << 1) <= n:
            k <<= 1

        return (k << 1) - 1 - self.minimumOneBitOperations(k ^ n)

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(\log n)$ for recursion stack.

2. Math (Iteration) - I

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        res = 0
        k = 1 << 30
        sign = 1

        while n:
            while k > n:
                k >>= 1

            res += (sign * ((k << 1) - 1))
            sign *= -1
            n ^= k

        return res

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

3. Math (Iteration) - II

class Solution:
    def minimumOneBitOperations(self, n: int) -> int:
        res, sign = 0, 1
        while n:
            res += sign * (n ^ (n - 1))
            n &= (n - 1)
            sign *= -1
        return abs(res)

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$

4. Math (Grey Code)

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

Time & Space Complexity

Time complexity: $O(\log n)$
Space complexity: $O(1)$