# Minimum Operations to Convert Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-convert-number)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-convert-number
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array
---
## Problem
You are given a **0-indexed** integer array `nums` containing **distinct** numbers, an integer `start`, and an integer `goal`. There is an integer `x` that is initially set to `start`, and you want to perform operations on `x` such that it is converted to `goal`. You can perform the following operation repeatedly on the number `x`:

If `0 <= x <= 1000`, then for any index `i` in the array (`0 <= i < nums.length`), you can set `x` to any of the following:

* `x + nums[i]`
* `x - nums[i]`
* `x ^ nums[i]` (bitwise-XOR)

Note that you can use each `nums[i]` any number of times in any order. Operations that set `x` to be out of the range `0 <= x <= 1000` are valid, but no more operations can be done afterward.

Return _the **minimum** number of operations needed to convert_ `x = start` _into_ `goal`_, and_ `-1` _if it is not possible_.

**Example 1:**

**Input:** nums = [2,4,12], start = 2, goal = 12
**Output:** 2
**Explanation:** We can go from 2 → 14 → 12 with the following 2 operations.
- 2 + 12 = 14
- 14 - 2 = 12

**Example 2:**

**Input:** nums = [3,5,7], start = 0, goal = -4
**Output:** 2
**Explanation:** We can go from 0 → 3 → -4 with the following 2 operations. 
- 0 + 3 = 3
- 3 - 7 = -4
Note that the last operation sets x out of the range 0 <= x <= 1000, which is valid.

**Example 3:**

**Input:** nums = [2,8,16], start = 0, goal = 1
**Output:** -1
**Explanation:** There is no way to convert 0 into 1.

**Constraints:**

* `1 <= nums.length <= 1000`
* `-109 <= nums[i], goal <= 109`
* `0 <= start <= 1000`
* `start != goal`
* All the integers in `nums` are distinct.

# Approaches
## Breadth-First Search (BFS)
This problem can be modeled as finding the shortest path in an unweighted graph. The numbers we can reach are the nodes, and the three operations (`+`, `-`, `^`) for each number in `nums` represent the edges. Breadth-First Search (BFS) is the ideal algorithm for finding the shortest path in an unweighted graph because it explores the graph level by level. This guarantees that the first time we reach the `goal`, it will be through the minimum number of operations.
**Time:** O(N * M), where N is the range of valid numbers (1001) and M is the length of the `nums` array. In the worst case, we visit each of the N numbers once, and for each, we iterate through M numbers in `nums` to generate new states. · **Space:** O(N), where N is the range of valid numbers (1001). The space is used for the queue and the `visited` array, both of which can store up to N elements.
**Pros:** Guaranteed to find the minimum number of operations.; Relatively straightforward to implement.; Efficient enough to pass within the given constraints.
**Cons:** May explore a large number of states if the shortest path is long.; Can be less efficient than a bidirectional search for certain graph structures.
### Explanation
The core of this approach is a systematic, level-by-level exploration of all reachable numbers starting from `start`. We use a queue to manage the numbers to visit, ensuring a breadth-first traversal. A `visited` array is crucial to prevent cycles and avoid redundant computations by ensuring each number between 0 and 1000 is processed at most once.

The search begins with the `start` number at level 0. In each subsequent step (level), we generate all possible numbers that can be reached from the numbers in the current level by applying one of the three operations with every element of `nums`. If any of these newly generated numbers is the `goal`, we have found our solution. If a new number is within the valid range `[0, 1000]` and hasn't been visited, we add it to the queue for future exploration. This process continues until the `goal` is found or the queue is empty, which signifies that the `goal` is unreachable.

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

class Solution {
    public int minimumOperations(int[] nums, int start, int goal) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[1001];

        queue.offer(start);
        visited[start] = true;

        int operations = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            operations++;

            for (int i = 0; i < levelSize; i++) {
                int currentX = queue.poll();

                for (int num : nums) {
                    // Operation 1: x + num
                    int next1 = currentX + num;
                    if (next1 == goal) {
                        return operations;
                    }
                    if (next1 >= 0 && next1 <= 1000 && !visited[next1]) {
                        visited[next1] = true;
                        queue.offer(next1);
                    }

                    // Operation 2: x - num
                    int next2 = currentX - num;
                    if (next2 == goal) {
                        return operations;
                    }
                    if (next2 >= 0 && next2 <= 1000 && !visited[next2]) {
                        visited[next2] = true;
                        queue.offer(next2);
                    }

                    // Operation 3: x ^ num
                    int next3 = currentX ^ num;
                    if (next3 == goal) {
                        return operations;
                    }
                    if (next3 >= 0 && next3 <= 1000 && !visited[next3]) {
                        visited[next3] = true;
                        queue.offer(next3);
                    }
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
- Create a queue and add the `start` value.
- Create a `visited` boolean array of size 1001 to keep track of visited numbers in the range `[0, 1000]`. Mark `start` as visited.
- Initialize an `operations` counter to 0.
- While the queue is not empty, perform a level-order traversal:
  - Get the number of elements in the current level (`levelSize`).
  - Increment the `operations` counter.
  - For `i` from 0 to `levelSize - 1`:
    - Dequeue the current number `x`.
    - For each `num` in the `nums` array:
      - Calculate the three possible next numbers: `next_add = x + num`, `next_sub = x - num`, and `next_xor = x ^ num`.
      - For each of these `next_val`:
        - If `next_val` equals `goal`, the shortest path is found. Return the current `operations` count.
        - If `next_val` is within the range `[0, 1000]` and has not been visited:
          - Mark `next_val` as visited.
          - Enqueue `next_val`.
- If the queue becomes empty and the `goal` has not been reached, it is impossible to convert `start` to `goal`. Return -1.

## Bidirectional Breadth-First Search (Bi-BFS)
Bidirectional BFS is an optimization of the standard BFS approach. It works by running two simultaneous BFS searches—one forward from the `start` node and one backward from the `goal` node. The algorithm terminates when the two search frontiers intersect. By searching from both ends, the total number of explored states can be drastically reduced from O(b^d) to O(2 * b^(d/2)), where `b` is the branching factor and `d` is the path length. This makes it much faster, especially for problems with long solution paths.
**Time:** O(N * M) in the worst case, same as standard BFS. However, its average-case performance is significantly better at O(M * b^(d/2)), where `b` is the branching factor and `d` is the shortest path length. · **Space:** O(N), where N is the range of valid numbers (1001). In the worst case, both distance maps could store up to N/2 elements. On average, the space is O(b^(d/2)), which is much better than standard BFS.
**Pros:** Potentially much faster than standard BFS by reducing the search space exponentially.; Optimal for finding shortest paths in large graphs where the path length is significant.
**Cons:** Significantly more complex to implement than a standard BFS.; Only provides a performance benefit if the `goal` is within the valid range `[0, 1000]`.; Requires more memory to maintain two queues and two distance/visited structures.
### Explanation
This approach is only feasible when the operations are reversible and the `goal` itself is a valid starting point for a search (i.e., within the `[0, 1000]` range). Fortunately, the given operations are reversible: the reverse of `+ num` is `- num`, `- num` is `+ num`, and `^ num` is its own inverse.

If the `goal` is outside the valid range, we cannot start a backward search from it, so we must revert to a standard BFS. Assuming `goal` is in range, we maintain two queues and two distance maps. In each step, we expand the smaller of the two search frontiers to keep the search balanced. When expanding a node `x` from the start-search, we check if any of its neighbors have already been visited by the goal-search. If a meeting point is found, we can combine the distances from both searches to get the total minimum operations.

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

class Solution {
    public int minimumOperations(int[] nums, int start, int goal) {
        // Fallback to standard BFS if goal is out of range for a Bi-BFS starting point.
        if (goal < 0 || goal > 1000) {
            return standardBfs(nums, start, goal);
        }

        Queue<Integer> qStart = new LinkedList<>();
        Map<Integer, Integer> distStart = new HashMap<>();
        qStart.offer(start);
        distStart.put(start, 0);

        Queue<Integer> qGoal = new LinkedList<>();
        Map<Integer, Integer> distGoal = new HashMap<>();
        qGoal.offer(goal);
        distGoal.put(goal, 0);

        int ops = 0;
        while (!qStart.isEmpty() && !qGoal.isEmpty()) {
            ops++;
            // Always expand the smaller queue to keep search balanced
            if (qStart.size() <= qGoal.size()) {
                int result = expandQueue(qStart, distStart, distGoal, nums, ops);
                if (result != -1) return result;
            } else {
                int result = expandQueue(qGoal, distGoal, distStart, nums, ops);
                if (result != -1) return result;
            }
        }

        return -1;
    }

    private int expandQueue(Queue<Integer> queue, Map<Integer, Integer> dist, Map<Integer, Integer> otherDist, int[] nums, int ops) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            int current = queue.poll();

            for (int num : nums) {
                int[] nextStates = {current + num, current - num, current ^ num};

                for (int next : nextStates) {
                    if (otherDist.containsKey(next)) {
                        return ops + otherDist.get(next);
                    }
                    if (next >= 0 && next <= 1000 && !dist.containsKey(next)) {
                        dist.put(next, ops);
                        queue.offer(next);
                    }
                }
            }
        }
        return -1;
    }

    // Standard BFS for fallback when goal is out of bounds
    private int standardBfs(int[] nums, int start, int goal) {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[1001];
        if(start >= 0 && start <= 1000) {
            queue.offer(start);
            visited[start] = true;
        }
        int operations = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            operations++;
            for (int i = 0; i < levelSize; i++) {
                int currentX = queue.poll();
                for (int num : nums) {
                    int[] nextStates = {currentX + num, currentX - num, currentX ^ num};
                    for (int next : nextStates) {
                        if (next == goal) return operations;
                        if (next >= 0 && next <= 1000 && !visited[next]) {
                            visited[next] = true;
                            queue.offer(next);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
```
### Algorithm
- First, check if `goal` is within the valid range `[0, 1000]`. If not, this approach is not applicable, and we should fall back to a standard BFS.
- Initialize two queues: `q_start` with `start` and `q_goal` with `goal`.
- Initialize two distance maps (or arrays): `dist_start` to store distances from `start`, and `dist_goal` to store distances from `goal`. Initialize `dist_start[start] = 0` and `dist_goal[goal] = 0`.
- In a loop, as long as both queues are non-empty:
  - To keep the search balanced, choose to expand the smaller of the two queues.
  - Let's say we expand `q_start`. Dequeue a node `x`.
  - For each `num` in `nums`, generate the three next states (`x+num`, `x-num`, `x^num`).
  - For each `next_x`:
    - Check if `next_x` has been visited by the backward search (i.e., exists in `dist_goal`). If so, a meeting point is found. The total operations are `dist_start[x] + 1 + dist_goal[next_x]`. Return this value.
    - If `next_x` is valid and not yet in `dist_start`, add it to `q_start` and record its distance.
  - Perform a similar expansion for `q_goal`, using the reverse operations.
- If the loop terminates because a queue is empty, no path exists. Return -1.

# Solutions
### Java

```java
class Solution { public int minimumOperations ( int [] nums , int start , int goal ) { IntBinaryOperator op1 = ( x , y ) -> x + y ; IntBinaryOperator op2 = ( x , y ) -> x - y ; IntBinaryOperator op3 = ( x , y ) -> x ^ y ; IntBinaryOperator [] ops = { op1 , op2 , op3 }; boolean [] vis = new boolean [ 1001 ]; Queue < int []> queue = new ArrayDeque <>(); queue . offer ( new int [] { start , 0 }); while (! queue . isEmpty ()) { int [] p = queue . poll (); int x = p [ 0 ], step = p [ 1 ]; for ( int num : nums ) { for ( IntBinaryOperator op : ops ) { int nx = op . applyAsInt ( x , num ); if ( nx == goal ) { return step + 1 ; } if ( nx >= 0 && nx <= 1000 && ! vis [ nx ]) { queue . offer ( new int [] { nx , step + 1 }); vis [ nx ] = true ; } } } } return - 1 ; } }
```

### CPP

```cpp
class Solution { public: int minimumOperations ( vector < int >& nums , int start , int goal ) { using pii = pair < int , int > ; vector < function < int ( int , int ) >> ops { []( int x , int y ) { return x + y ; }, []( int x , int y ) { return x - y ; }, []( int x , int y ) { return x ^ y ; }, }; vector < bool > vis ( 1001 , false ); queue < pii > q ; q . push ({ start , 0 }); while ( ! q . empty ()) { auto [ x , step ] = q . front (); q . pop (); for ( int num : nums ) { for ( auto op : ops ) { int nx = op ( x , num ); if ( nx == goal ) { return step + 1 ; } if ( nx >= 0 && nx <= 1000 && ! vis [ nx ]) { q . push ({ nx , step + 1 }); vis [ nx ] = true ; } } } } return - 1 ; } };
```

### Python

```python
class Solution : def minimumOperations ( self , nums : List [ int ], start : int , goal : int ) -> int : op1 = lambda x , y : x + y op2 = lambda x , y : x - y op3 = lambda x , y : x ^ y ops = [ op1 , op2 , op3 ] vis = [ False ] * 1001 q = deque ([( start , 0 )]) while q : x , step = q . popleft () for num in nums : for op in ops : nx = op ( x , num ) if nx == goal : return step + 1 if 0 <= nx <= 1000 and not vis [ nx ]: q . append (( nx , step + 1 )) vis [ nx ] = True return - 1
```