What is the time complexity of LeetCode 1611. Minimum One Bit Operations to Make Integers Zero?

The Python solution on this page runs in O(\log n), where n is the integer given in the problem.

What is the space complexity of LeetCode 1611. Minimum One Bit Operations to Make Integers Zero?

The Python solution on this page uses O(1) auxiliary space.

Minimum One Bit Operations to Make Integers Zero — LeetCode 1611 Python Solution

HardBit ManipulationMemoizationDynamic Programming

Problem: #1611
Pattern: Bit Manipulation
Reading time: 2 min
Source: leetcode.com

The problem

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.

Example

Input: n = 3
Output: 2
Explanation: The binary representation of 3 is "11".

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(\log n), where n is the integer given in the problem
Space	O(1) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1611. Minimum One Bit Operations to Make Integers Zero is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1611. Minimum One Bit Operations to Make Integers Zero?: LeetCode 1611. Minimum One Bit Operations to Make Integers Zero is rated Hard on LeetCode.
What is the time complexity of LeetCode 1611. Minimum One Bit Operations to Make Integers Zero?: The Python solution on this page runs in O(\log n), where n is the integer given in the problem.
What is the space complexity of LeetCode 1611. Minimum One Bit Operations to Make Integers Zero?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 1611. Minimum One Bit Operations to Make Integers Zero cover?: LeetCode 1611. Minimum One Bit Operations to Make Integers Zero is tagged Bit Manipulation, Memoization and Dynamic Programming on LeetCode.