1611. Minimum One Bit Operations to Make Integers Zero

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-1}B_{n-2}...B_2B_1B_0\), and its Gray code representation is \(G_{n-1}G_{n-2}...G_2G_1G_0\). 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} \cdots \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)\).

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7
8
9

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6

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

1
2
3
4
5
6
7

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

Comments