##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2059.html

# 2059. Minimum Operations to Convert Number (Medium)

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 = [1,3], start = 6, goal = 4Output:2Explanation:We can go from 6 → 7 → 4 with the following 2 operations. - 6 ^ 1 = 7 - 7 ^ 3 = 4

**Example 2:**

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

**Example 3:**

Input:nums = [3,5,7], start = 0, goal = -4Output:2Explanation: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 4:**

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

**Example 5:**

Input:nums = [1], start = 0, goal = 3Output:3Explanation:We can go from 0 → 1 → 2 → 3 with the following 3 operations. - 0 + 1 = 1 - 1 + 1 = 2 - 2 + 1 = 3

**Constraints:**

`1 <= nums.length <= 1000`

`-10`

^{9}<= nums[i], goal <= 10^{9}`0 <= start <= 1000`

`start != goal`

- All the integers in
`nums`

are distinct.

**Similar Questions**:

## Solution 1. BFS

```
// OJ: https://leetcode.com/problems/minimum-operations-to-convert-number/
// Time: O(1000 * N)
// Space: O(1000)
class Solution {
public:
int minimumOperations(vector<int>& A, int start, int goal) {
queue<int> q{ {start} };
bool seen[1001] = {};
seen[start] = true;
int step = 0;
while (q.size()) {
int cnt = q.size();
while (cnt--) {
int n = q.front();
q.pop();
for (int d : A) {
for (int next : {n + d, n - d, n ^ d}) {
if (next == goal) return step + 1;
if (next < 0 || next > 1000 || seen[next]) continue;
seen[next] = true;
q.push(next);
}
}
}
++step;
}
return -1;
}
};
```