RUST GYM Leetcode 1611 Minimum One Bit Operations to Make Integers Zero Rust Solution

1611. Minimum One Bit Operations to Make Integers Zero

Given an integer n, you must transform it into 0 using the following operations any number of times:

Change the rightmost (0^th) bit in the binary representation of n.
Change the i^th bit in the binary representation of n if the (i-1)^th bit is set to 1 and the (i-2)^th through 0^th bits are set to 0.

Return the minimum number of operations to transform n into 0.

Example 1:

Input: n = 0
Output: 0

Example 2:

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 3:

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.

Example 4:

Input: n = 9
Output: 14

Example 5:

Input: n = 333
Output: 393

Constraints:

0 <= n <= 10⁹

Rust Solution

struct Solution;

impl Solution {
    fn minimum_one_bit_operations(n: i32) -> i32 {
        if n <= 1 {
            n
        } else {
            let mut bit = 0;
            while 1 << bit <= n {
                bit += 1;
            }
            let m = n ^ (1 << (bit - 1));
            let k = (1 << bit) - 1;
            k - Solution::minimum_one_bit_operations(m)
        }
    }
}

#[test]
fn test() {
    let n = 0;
    let res = 0;
    assert_eq!(Solution::minimum_one_bit_operations(n), res);
    let n = 3;
    let res = 2;
    assert_eq!(Solution::minimum_one_bit_operations(n), res);
    let n = 6;
    let res = 4;
    assert_eq!(Solution::minimum_one_bit_operations(n), res);
}

Having problems with this solution? Click here to submit an issue on github.