1611. Minimum One Bit Operations to Make Integers Zero LeetCode Solution

In this guide, you will get 1611. Minimum One Bit Operations to Make Integers Zero LeetCode Solution with the best time and space complexity. The solution to Minimum One Bit Operations to Make Integers Zero problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum One Bit Operations to Make Integers Zero solution in C++
Minimum One Bit Operations to Make Integers Zero solution in Java
Minimum One Bit Operations to Make Integers Zero solution in Python
Additional Resources

1611. Minimum One Bit Operations to Make Integers Zero LeetCode Solution image

Problem Statement of 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 (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

Complexity Analysis

Time Complexity: O(\log n)
Space Complexity: O(\log n)

1611. Minimum One Bit Operations to Make Integers Zero LeetCode Solution in C++

class Solution {
 public:
  int minimumOneBitOperations(int n) {
    // Observation: e.g. n = 2^2
    //        100 (2^2 needs 2^3 - 1 ops)
    // op1 -> 101
    // op2 -> 111
    // op1 -> 110
    // op2 -> 010 (2^1 needs 2^2 - 1 ops)
    // op1 -> 011
    // op2 -> 001 (2^0 needs 2^1 - 1 ops)
    // op1 -> 000
    //
    // So 2^k needs 2^(k + 1) - 1 ops. Note this is reversible, i.e., 0 -> 2^k
    // also takes 2^(k + 1) - 1 ops.

    // e.g. n = 1XXX, our first goal is to change 1XXX -> 1100.
    //   - If the second bit is 1, you only need to consider the cost of turning
    //     the last 2 bits to 0.
    //   - If the second bit is 0, you need to add up the cost of flipping the
    //     second bit from 0 to 1.
    // XOR determines the cost minimumOneBitOperations(1XXX^1100) accordingly.
    // Then, 1100 -> 0100 needs 1 op. Finally, 0100 -> 0 needs 2^3 - 1 ops.
    if (n == 0)
      return 0;
    // x is the largest 2^k <= n.
    // x | x >> 1 -> x >> 1 needs 1 op.
    //     x >> 1 -> 0      needs x = 2^k - 1 ops.
    int x = 1;
    while (x * 2 <= n)
      x <<= 1;
    return minimumOneBitOperations(n ^ (x | x >> 1)) + 1 + x - 1;
  }
};
/* code provided by PROGIEZ */

1611. Minimum One Bit Operations to Make Integers Zero LeetCode Solution in Java

class Solution {
  public int minimumOneBitOperations(int n) {
    // Observation: e.g. n = 2^2
    //        100 (2^2 needs 2^3 - 1 ops)
    // op1 -> 101
    // op2 -> 111
    // op1 -> 110
    // op2 -> 010 (2^1 needs 2^2 - 1 ops)
    // op1 -> 011
    // op2 -> 001 (2^0 needs 2^1 - 1 ops)
    // op1 -> 000
    //
    // So 2^k needs 2^(k + 1) - 1 ops. Note this is reversible, i.e., 0 -> 2^k
    // also takes 2^(k + 1) - 1 ops.

    // e.g. n = 1XXX, our first goal is to change 1XXX -> 1100.
    //   - If the second bit is 1, you only need to consider the cost of turning
    //     the last 2 bits to 0.
    //   - If the second bit is 0, you need to add up the cost of flipping the
    //     second bit from 0 to 1.
    // XOR determines the cost minimumOneBitOperations(1XXX^1100) accordingly.
    // Then, 1100 -> 0100 needs 1 op. Finally, 0100 -> 0 needs 2^3 - 1 ops.
    if (n == 0)
      return 0;
    // x is the largest 2^k <= n.
    // x | x >> 1 -> x >> 1 needs 1 op.
    //     x >> 1 -> 0      needs x = 2^k - 1 ops.
    int x = 1;
    while (x * 2 <= n)
      x <<= 1;
    return minimumOneBitOperations(n ^ (x | x >> 1)) + 1 + x - 1;
  }
}
// code provided by PROGIEZ

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

class Solution:
  def minimumOneBitOperations(self, n: int) -> int:
    # Observation: e.g. n = 2^2
    #        100 (2^2 needs 2^3 - 1 ops)
    # op1 -> 101
    # op2 -> 111
    # op1 -> 110
    # op2 -> 010 (2^1 needs 2^2 - 1 ops)
    # op1 -> 011
    # op2 -> 001 (2^0 needs 2^1 - 1 ops)
    # op1 -> 000
    #
    # So 2^k needs 2^(k + 1) - 1 ops. Note this is reversible, i.e., 0 -> 2^k
    # also takes 2^(k + 1) - 1 ops.

    # e.g. n = 1XXX, our first goal is to change 1XXX -> 1100.
    #   - If the second bit is 1, you only need to consider the cost of turning
    #     the last 2 bits to 0.
    #   - If the second bit is 0, you need to add up the cost of flipping the
    #     second bit from 0 to 1.
    # XOR determines the cost minimumOneBitOperations(1XXX^1100) accordingly.
    # Then, 1100 -> 0100 needs 1 op. Finally, 0100 -> 0 needs 2^3 - 1 ops.
    if n == 0:
      return 0
    # x is the largest 2^k <= n.
    # x | x >> 1 -> x >> 1 needs 1 op.
    #     x >> 1 -> 0      needs x = 2^k - 1 ops.
    x = 1 << n.bit_length() - 1
    return self.minimumOneBitOperations(n ^ (x | x >> 1)) + 1 + x - 1
 # code by PROGIEZ