# Minimum One Bit Operations to Make Integers Zero
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-one-bit-operations-to-make-integers-zero)
Canonical: https://scaleengineer.com/dsa/problems/minimum-one-bit-operations-to-make-integers-zero
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Memoization](https://scaleengineer.com/dsa/patterns/memoization)
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [ServiceNow](https://scaleengineer.com/companies/servicenow), [McKinsey](https://scaleengineer.com/companies/mckinsey)
---
## 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`.

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`

# Approaches
## Recursive Approach based on Recurrence Relation
This approach is based on establishing a recurrence relation that defines the solution for `n` in terms of a solution for a smaller number. By analyzing the structure of the operations, we can find a relationship between the operations needed for a number `n` and the operations for the number `m` that remains after removing `n`'s most significant bit (MSB).
**Time:** O(log n). The number of recursive calls is at most the number of bits in `n`. Finding the MSB inside each call also takes logarithmic time relative to the value of `n` in that call. · **Space:** O(log n), due to the recursion stack depth, which is at most the number of bits in `n`.
**Pros:** The code is a direct translation of the mathematical recurrence, making it relatively easy to understand if the recurrence is known.; It correctly solves the problem by breaking it down into smaller subproblems.
**Cons:** Incurs overhead from recursive function calls.; Uses stack space proportional to the number of bits in `n`, which could be a concern for extremely large numbers (though not an issue with the given constraints).
### Explanation
Let `f(n)` be the minimum number of operations to convert `n` to 0. We can derive a recurrence relation by considering the MSB of `n`. Let the MSB be at position `k`, so `n = 2^k + m` where `m < 2^k`. To turn off the `k`-th bit, we must first transform the number into the form `...1100...0`, specifically `2^k + 2^(k-1)`. This involves transforming `m` to `2^(k-1)`. After flipping the `k`-th bit, we are left with `2^(k-1)`, which we then need to transform to 0. A deep analysis of this process reveals a surprisingly simple recurrence relation: `f(2^k + m) = (2^(k+1) - 1) - f(m)`. The base case is `f(0) = 0`. This relation can be implemented directly using a recursive function.

```java
class Solution {
    public int minimumOneBitOperations(int n) {
        if (n == 0) {
            return 0;
        }

        // Find k, the position of the most significant bit.
        // For n > 0, k = floor(log2(n)).
        int k = 0;
        while ((1 << (k + 1)) <= n && (1 << (k + 1)) > 0) {
            k++;
        }

        // m is the remaining part of n after removing the MSB.
        int m = n - (1 << k);

        // The recurrence relation is f(n) = (2^(k+1) - 1) - f(m)
        // where n = 2^k + m.
        return ((1 << (k + 1)) - 1) - minimumOneBitOperations(m);
    }
}
```
### Algorithm
1. Define a recursive function, let's call it `solve(n)`.
2. The base case for the recursion is `solve(0) = 0`.
3. For any `n > 0`, find the position of its most significant bit (MSB), let's say `k`. This means `2^k <= n < 2^(k+1)`.
4. The number `n` can be expressed as `n = 2^k + m`, where `m = n - 2^k`.
5. The recurrence relation is `solve(n) = (2^(k+1) - 1) - solve(m)`.
6. The function computes this value and returns it. The initial call is `solve(n)`.

## Iterative Approach based on Recurrence Relation
This approach optimizes the recursive solution by converting it into an iterative process. By unrolling the recursion, we can eliminate the function call overhead and the need for stack space, thus improving space efficiency. The same underlying recurrence relation, `f(2^k + m) = (2^{k+1} - 1) - f(m)`, is used, but it's applied iteratively.
**Time:** O(log n). The loop runs once for each set bit in `n`. In the worst case, it runs `log n` times. Finding the MSB in each step also contributes to the logarithmic complexity. · **Space:** O(1), as we only use a few variables to store the state.
**Pros:** More space-efficient than the recursive approach as it uses constant extra space.; Avoids potential stack overflow errors for very large inputs.; Generally faster due to the absence of function call overhead.
**Cons:** The logic behind the iterative update `ans = (2^(k+1) - 1) - ans` might be less intuitive to derive compared to the recursive formulation.
### Explanation
The recursive structure can be transformed into a loop that processes the bits of `n` from most significant to least significant. We maintain a result variable that accumulates the answer according to the recurrence. In each iteration, we identify the MSB of the current value of `n`, apply the iterative formula derived from the recurrence, and then strip off that MSB to prepare for the next iteration. This continues until `n` becomes 0.

```java
class Solution {
    public int minimumOneBitOperations(int n) {
        int ans = 0;
        while (n > 0) {
            // Find k, the position of the most significant bit.
            int k = 0;
            while ((1 << (k + 1)) <= n && (1 << (k + 1)) > 0) {
                k++;
            }

            // Apply the iterative version of the recurrence.
            // This formula is derived by unrolling the recursion.
            ans = ((1 << (k + 1)) - 1) - ans;

            // Remove the MSB from n for the next iteration.
            n -= (1 << k);
        }
        return ans;
    }
}
```
### Algorithm
1. Initialize a result variable, `ans`, to 0.
2. Loop as long as `n` is greater than 0.
3. Inside the loop, find the position `k` of the most significant bit (MSB) of the current `n`.
4. Update the result using the formula: `ans = (2^(k+1) - 1) - ans`.
5. Remove the MSB from `n` to process the next part of the number: `n = n - 2^k` (or `n = n XOR 2^k`).
6. After the loop terminates, `ans` holds the final result.

## Gray Code Conversion
This highly efficient approach is based on the insight that the problem is equivalent to converting a number from Gray code to its standard binary representation. The sequence of numbers generated by the allowed operations follows the binary-reflected Gray code sequence. The number of operations to transform `n` to `0` is simply the index of `n` in this sequence. This index can be found using a clever bitwise algorithm.
**Time:** O(log n), as the loop runs once for each bit in the number `n`. · **Space:** O(1), using only a single extra variable for the result.
**Pros:** Extremely efficient in both time and space.; The implementation is very concise and elegant.; It is one of the fastest possible solutions due to its direct computation using simple bitwise operations.
**Cons:** The connection to Gray codes is not immediately obvious from the problem statement and requires a deeper insight into the problem's structure.
### Explanation
The operations defined in the problem correspond to moving between adjacent values in a Gray code sequence. The `k`-th number in this sequence (starting from `k=0`) is `G(k) = k XOR (k >> 1)`. The problem asks for the minimum operations to get from `n` to `0`, which is the index `k` such that `G(k) = n`. We need to find `k` given `n`. This is the inverse operation of generating a Gray code.

The binary representation `k` can be recovered from its Gray code `n` using the following relations:
- The most significant bit of `k` is the same as the MSB of `n`.
- For any other bit `i`, `k_i = n_i XOR k_{i+1}`.

This can be computed efficiently with a loop: `k = n XOR (n >> 1) XOR (n >> 2) XOR ...`. This series of XORs can be calculated with a simple loop.

```java
class Solution {
    public int minimumOneBitOperations(int n) {
        int result = n;
        // The loop computes result = n ^ (n >> 1) ^ (n >> 2) ^ ...
        // In each step, n is right-shifted, and the result is updated.
        while ((n >>= 1) > 0) {
            result ^= n;
        }
        return result;
    }
}
```
### Algorithm
1. Initialize a result variable, `result`, with the value of `n`.
2. Create a loop that continues as long as `n` shifted to the right is greater than 0.
3. In each iteration, right-shift `n` by one bit (`n >>= 1`).
4. XOR the `result` with the new value of `n` (`result ^= n`).
5. After the loop finishes, `result` will hold the binary representation corresponding to the Gray code `n`, which is the minimum number of operations.

# Solutions
### Java

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

```

### CPP

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

```

### Python

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

```