# Minimum Operations to Reduce an Integer to 0
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-reduce-an-integer-to-0)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-reduce-an-integer-to-0
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation)
**Companies:** [IBM](https://scaleengineer.com/companies/ibm), [Nvidia](https://scaleengineer.com/companies/nvidia), [Two Sigma](https://scaleengineer.com/companies/two-sigma)
---
## Problem
You are given a positive integer `n`, you can do the following operation **any** number of times:

* Add or subtract a **power** of `2` from `n`.

Return _the **minimum** number of operations to make_ `n` _equal to_ `0`.

A number `x` is power of `2` if `x == 2i` where `i >= 0`_._

**Example 1:**

**Input:** n = 39
**Output:** 3
**Explanation:** We can do the following operations:
- Add 20 = 1 to n, so now n = 40.
- Subtract 23 = 8 from n, so now n = 32.
- Subtract 25 = 32 from n, so now n = 0.
It can be shown that 3 is the minimum number of operations we need to make n equal to 0.

**Example 2:**

**Input:** n = 54
**Output:** 3
**Explanation:** We can do the following operations:
- Add 21 = 2 to n, so now n = 56.
- Add 23 = 8 to n, so now n = 64.
- Subtract 26 = 64 from n, so now n = 0.
So the minimum number of operations is 3.

**Constraints:**

* `1 <= n <= 105`

# Approaches
## Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in an unweighted graph. The nodes of the graph are integers, and an edge exists between two numbers if one can be transformed into the other by adding or subtracting a power of 2. Since each operation has a uniform cost of 1, Breadth-First Search (BFS) is a suitable algorithm to find the minimum number of operations, which corresponds to the shortest path from `n` to `0`.
**Time:** O(N * log N), where N is the size of the search space (e.g., `2*n`). From each number, we can transition to O(log N) other numbers. · **Space:** O(N), where N is the size of the search space. With the heuristic bound, this is O(n) for the queue and the visited set.
**Pros:** Conceptually straightforward as it directly models the problem as a shortest path search.; Guaranteed to find the minimum number of operations because BFS explores the graph layer by layer.
**Cons:** Can be slow and memory-intensive for large `n` due to the potentially large search space.; The efficiency relies on choosing a good heuristic for the search boundary. A loose boundary increases computation, while a tight one might miss the optimal path.
### Explanation
We start a BFS from the number `n` with the goal of reaching `0`. A queue is used to manage the numbers to visit, and a set keeps track of visited numbers to prevent cycles and redundant work. The state in the queue can simply be the number, as BFS naturally explores layer by layer, with each layer corresponding to one additional operation.

We begin with `n` in the queue and a distance of 0. In each step, we dequeue a number `curr`. If `curr` is 0, we've found the shortest path, and the current distance is the answer. Otherwise, we generate all possible next states by adding or subtracting powers of 2 (`2^i`). For each new, unvisited number, we enqueue it. To keep the search space manageable, we can bound the numbers we explore, for instance, between 0 and `2*n`. This is a reasonable heuristic, as optimal paths are unlikely to involve numbers much larger than the starting number `n`.

```java
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int minOperations(int n) {
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        queue.offer(n);
        visited.add(n);
        
        int operations = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int current = queue.poll();
                
                if (current == 0) {
                    return operations;
                }
                
                // Iterate through powers of 2
                for (int j = 0; (1 << j) <= 2 * n + 1; j++) {
                    int powerOfTwo = 1 << j;
                    
                    int nextAdd = current + powerOfTwo;
                    // A heuristic bound to keep the search space reasonable
                    if (!visited.contains(nextAdd) && nextAdd >= 0 && nextAdd < 2 * n + 2) { 
                        visited.add(nextAdd);
                        queue.offer(nextAdd);
                    }
                    
                    int nextSub = current - powerOfTwo;
                    if (nextSub >= 0 && !visited.contains(nextSub)) {
                        visited.add(nextSub);
                        queue.offer(nextSub);
                    }
                }
            }
            operations++;
        }
        
        return -1; // Should not be reached given the problem constraints
    }
}
```
### Algorithm
- Create a queue and add the starting number `n`.
- Create a `visited` set to store numbers that have been processed to avoid cycles.
- Initialize `operations` count to 0.
- Begin a loop that continues as long as the queue is not empty. This loop represents levels in the BFS.
- In each level, process all numbers currently in the queue.
- For each number `current` dequeued:
  - If `current` is 0, the target is reached. Return the current `operations` count.
  - Generate neighbors by adding and subtracting all relevant powers of 2 (`2^i`).
  - For each neighbor, if it has not been visited and is within a reasonable bound (e.g., `0` to `2*n`), add it to the queue and the `visited` set.
- After processing all nodes at a level, increment the `operations` count.

## Recursion with Memoization (Top-Down DP)
A more efficient approach involves analyzing the problem's structure to find a recurrence relation. We can define a function `solve(n)` that computes the minimum operations for a given integer `n`. By observing the properties of the operations on even and odd numbers, we can establish this relation. To avoid re-computing results for the same numbers, we use memoization (a top-down dynamic programming technique).
**Time:** O(log n). The number of distinct states `k` for which `solve(k)` is computed is proportional to `log n`, as `n` is roughly halved at each step of the recursion. · **Space:** O(log n), for the recursion stack depth and the size of the memoization map. The number of states we need to store is proportional to `log n`.
**Pros:** Significantly faster than BFS because it prunes the search space by exploiting the problem's mathematical structure.; The number of states to compute is logarithmic with respect to `n`.
**Cons:** A naive recursive implementation without memoization would be extremely slow due to re-computing the same subproblems.; For extremely large values of `n` (beyond the problem constraints), recursion could lead to a stack overflow error.
### Explanation
Let `solve(n)` be the minimum operations to reduce `n` to 0.

- **Base Case:** `solve(0) = 0`.
- **Recurrence Relation:**
  - If `n` is **even**, any operation `n ± 2^i` (for `i > 0`) corresponds to an operation on `n/2`. For example, `n - 2^i = 2 * (n/2 - 2^(i-1))`. The path from `n` to 0 effectively mirrors a path from `n/2` to 0, so `solve(n) = solve(n/2)`. We can simply shift our focus to `n/2` without an operation cost.
  - If `n` is **odd**, we must use an operation involving `2^0 = 1` to make it even. We can either go to `n-1` or `n+1`. The cost is 1 (for this operation) plus the minimum operations from the resulting state. So, `solve(n) = 1 + min(solve(n-1), solve(n+1))`. Since both `n-1` and `n+1` are even, this simplifies to `solve(n) = 1 + min(solve((n-1)/2), solve((n+1)/2))`. 

This recursive structure is implemented with a helper map for memoization to store the results of `solve(n)` once computed.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    private Map<Integer, Integer> memo = new HashMap<>();

    public int minOperations(int n) {
        if (n == 0) {
            return 0;
        }
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        int result;
        if ((n & 1) == 0) { // n is even
            // No operation cost, just reducing the problem size
            result = minOperations(n / 2);
        } else { // n is odd
            // Cost is 1 plus the minimum of the two choices
            int res1 = minOperations(n - 1);
            int res2 = minOperations(n + 1);
            result = 1 + Math.min(res1, res2);
        }
        
        memo.put(n, result);
        return result;
    }
}
```
### Algorithm
- Define a recursive function, say `solve(n)`, that returns the minimum operations for `n`.
- Use a map for memoization to store the results of `solve(n)`.
- Base Case: `solve(0)` is 0.
- Recursive Step:
  - If `n` is even, the problem reduces to solving for `n/2`. So, `solve(n) = solve(n/2)`.
  - If `n` is odd, we must perform an operation to make it even. The choices are `n-1` and `n+1`. The cost is 1 plus the minimum operations for the resulting state. Thus, `solve(n) = 1 + min(solve(n-1), solve(n+1))`. Since `n-1` and `n+1` are even, this is equivalent to `1 + min(solve((n-1)/2), solve((n+1)/2))`.
- In the function, first check the memoization table. If the result for `n` exists, return it. Otherwise, compute it using the recurrence, store it in the table, and then return it.

## Iterative Greedy Approach
The most efficient solution is an iterative approach based on a greedy strategy. This approach is derived from the insights gained from the recursive structure but eliminates the overhead of recursion and memoization. By analyzing the binary representation of `n`, we can make a locally optimal choice at each step that leads to the global optimum.
**Time:** O(log n). In each iteration, `n` is effectively reduced. If `n` is even, it's halved. If `n` is odd, it becomes `n±1` and is then halved in the next step. The number of iterations is proportional to the number of bits in `n`. · **Space:** O(1), as we only use a few variables to store the current number and the operation count.
**Pros:** Extremely fast, with a time complexity logarithmic in `n`.; Highly memory efficient, using only constant extra space.; It is the optimal solution for this problem.
**Cons:** The greedy logic is not immediately obvious and requires some analysis of the binary representations to prove its correctness.
### Explanation
The algorithm processes the number `n` by repeatedly looking at its least significant bits until `n` becomes 0.

- If `n` is **even**, its binary representation ends in a `0`. We can think of this as a "free" step, as we can simply right-shift `n` (`n = n / 2`) to process the next bit without adding to the operation count.

- If `n` is **odd**, its binary representation ends in a `1`. We must perform an operation. This costs 1 operation. The choice is between making `n` into `n-1` or `n+1`, both of which will be even. The greedy choice depends on which option leads to a state that can be resolved faster. 
  - If `n` ends in `...01` (i.e., `n % 4 == 1`), subtracting 1 gives `...00`. Adding 1 gives `...10`. The former is better as it clears two bits, which can then be shifted away. So we choose `n-1`.
  - If `n` ends in `...11` (i.e., `n % 4 == 3`), subtracting 1 gives `...10`. Adding 1 causes a carry, resulting in `...00` (and setting a higher bit). This is generally better as it clears a block of ones. So we choose `n+1`.
  - The number `n=3` (`11` in binary) is a special case where both `n-1=2` and `n+1=4` are powers of two, leading to the same total operation count. Our rule can be slightly adjusted to handle it, for instance, by grouping it with the `n-1` case.

This iterative process is highly efficient, requiring only a few variables.

```java
class Solution {
    public int minOperations(int n) {
        int ops = 0;
        while (n > 0) {
            if ((n & 1) == 0) {
                // n is even, LSB is 0. No operation needed for this bit.
                n >>= 1;
            } else {
                // n is odd, LSB is 1. An operation is required.
                ops++;
                // Greedy choice:
                // If n=3 or n ends in ...01, subtracting 1 is better or equal.
                // (n & 2) == 0 checks if the second bit is 0.
                if (n == 3 || (n & 2) == 0) {
                    n--;
                } else {
                    // n ends in ...11 (and is not 3), adding 1 is better.
                    n++;
                }
            }
        }
        return ops;
    }
}
```
### Algorithm
- Initialize an `operations` counter to 0.
- Loop as long as `n > 0`.
- Inside the loop:
  - If `n` is even (i.e., `n & 1 == 0`), its least significant bit is 0. No operation is needed for this bit. We can effectively handle higher bits by right-shifting `n` by one (`n >>= 1`).
  - If `n` is odd, we must perform an operation. Increment the `operations` counter.
    - We make a greedy choice based on the two least significant bits.
    - If `n` is 3, or if `n`'s binary representation ends in `...01` (`(n & 2) == 0`), the optimal move is to subtract 1. So, `n = n - 1`.
    - Otherwise, `n`'s binary representation must end in `...11` (`(n & 2) != 0`). The optimal move is to add 1. So, `n = n + 1`.
- Once the loop terminates (`n` becomes 0), return the total `operations` count.

# Solutions
### Java

```java
class Solution {
public
  int minOperations(int n) {
    int ans = 0, cnt = 0;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ++cnt;
      } else if (cnt > 0) {
        ++ans;
        cnt = cnt == 1 ? 0 : 1;
      }
    }
    ans += cnt == 1 ? 1 : 0;
    ans += cnt > 1 ? 2 : 0;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minOperations(int n) {
    int ans = 0, cnt = 0;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ++cnt;
      } else if (cnt > 0) {
        ++ans;
        cnt = cnt == 1 ? 0 : 1;
      }
    }
    ans += cnt == 1 ? 1 : 0;
    ans += cnt > 1 ? 2 : 0;
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minOperations(self, n: int) -> int: ans = cnt = 0 while n: if n & 1: cnt += 1 elif cnt: ans += 1 cnt = 0 if cnt == 1 else 1 n >>= 1 if cnt == 1: ans += 1 elif cnt > 1: ans += 2 return ans

```