Minimum Operations to Reduce an Integer to 0

• 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.

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.

1import java.util.HashSet;2import java.util.LinkedList;3import java.util.Queue;4import java.util.Set;5 6class Solution {7    public int minOperations(int n) {8        Queue<Integer> queue = new LinkedList<>();9        Set<Integer> visited = new HashSet<>();10        11        queue.offer(n);12        visited.add(n);13        14        int operations = 0;15        while (!queue.isEmpty()) {16            int levelSize = queue.size();17            for (int i = 0; i < levelSize; i++) {18                int current = queue.poll();19                20                if (current == 0) {21                    return operations;22                }23                24                // Iterate through powers of 225                for (int j = 0; (1 << j) <= 2 * n + 1; j++) {26                    int powerOfTwo = 1 << j;27                    28                    int nextAdd = current + powerOfTwo;29                    // A heuristic bound to keep the search space reasonable30                    if (!visited.contains(nextAdd) && nextAdd >= 0 && nextAdd < 2 * n + 2) { 31                        visited.add(nextAdd);32                        queue.offer(nextAdd);33                    }34                    35                    int nextSub = current - powerOfTwo;36                    if (nextSub >= 0 && !visited.contains(nextSub)) {37                        visited.add(nextSub);38                        queue.offer(nextSub);39                    }40                }41            }42            operations++;43        }44        45        return -1; // Should not be reached given the problem constraints46    }47}

• 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.

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.

1import java.util.HashMap;2import java.util.Map;3 4class Solution {5    private Map<Integer, Integer> memo = new HashMap<>();6 7    public int minOperations(int n) {8        if (n == 0) {9            return 0;10        }11        if (memo.containsKey(n)) {12            return memo.get(n);13        }14        15        int result;16        if ((n & 1) == 0) { // n is even17            // No operation cost, just reducing the problem size18            result = minOperations(n / 2);19        } else { // n is odd20            // Cost is 1 plus the minimum of the two choices21            int res1 = minOperations(n - 1);22            int res2 = minOperations(n + 1);23            result = 1 + Math.min(res1, res2);24        }25        26        memo.put(n, result);27        return result;28    }29}

• 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.

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.

1class Solution {2    public int minOperations(int n) {3        int ops = 0;4        while (n > 0) {5            if ((n & 1) == 0) {6                // n is even, LSB is 0. No operation needed for this bit.7                n >>= 1;8            } else {9                // n is odd, LSB is 1. An operation is required.10                ops++;11                // Greedy choice:12                // If n=3 or n ends in ...01, subtracting 1 is better or equal.13                // (n & 2) == 0 checks if the second bit is 0.14                if (n == 3 || (n & 2) == 0) {15                    n--;16                } else {17                    // n ends in ...11 (and is not 3), adding 1 is better.18                    n++;19                }20            }21        }22        return ops;23    }24}