LeetCode 1611. Minimum One Bit Operations to Make Integers Zero Solution in Java, C++, Python & More | Explanation + Code

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

Solutions

Solution 1: Gray Code Inverse Transform (Gray Code to Binary Code)

This problem essentially asks for the inverse transformation of Gray code at position n, i.e., constructing the original number from the Gray code.

Let's first review how to convert binary code to binary Gray code. The rule is to keep the most significant bit of the binary code as the most significant bit of the Gray code, while the second most significant bit of the Gray code is obtained by XORing the most significant bit and the second most significant bit of the binary code. The remaining bits of the Gray code are computed similarly to the second most significant bit.

Suppose a binary number is represented as B_n-1B_n-2...B_2B_1B₀, and its Gray code representation is G_n-1G_n-2...G_2G_1G₀. The most significant bit is kept, so G_n-1 = B_n-1; and for other bits G_i = B_i+1 \oplus B_i, where i=0,1,2..,n-2.

So what is the inverse transformation from Gray code to binary code?

We can observe that the most significant bit of the Gray code is kept, so B_n-1 = G_n-1; and B_n-2 = G_n-2 \oplus B_n-1 = G_n-2 \oplus G_n-1; and for other bits B_i = G_i \oplus G_i+1 … \oplus G_n-1, where i=0,1,2..,n-2. Therefore, we can use the following function rev(x) to obtain its binary code:

int rev(int x) {
    int n = 0;
    for (; x != 0; x >>= 1) {
        n ^= x;
    }
    return n;
}

The time complexity is O(log n), where n is the integer given in the problem. The space complexity is O(1).

PythonJavaC++GoTypeScriptRust

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

class Solution { public int minimumOneBitOperations(int n) { int ans = 0; for (; n > 0; n >>= 1) { ans ^= n; } return ans; } }(code-box)

class Solution { public: int minimumOneBitOperations(int n) { int ans = 0; for (; n > 0; n >>= 1) { ans ^= n; } return ans; } };(code-box)

func minimumOneBitOperations(n int) (ans int) { for ; n > 0; n >>= 1 { ans ^= n } return }(code-box)

function minimumOneBitOperations(n: number): number { let ans = 0; for (; n > 0; n >>= 1) { ans ^= n; } return ans; }(code-box)

impl Solution { pub fn minimum_one_bit_operations(mut n: i32) -> i32 { let mut ans = 0; while n > 0 { ans ^= n; n >>= 1; } ans } }(code-box)