BFS in Big-O of 3M steps

I'm sure this problem can be solved with DP, but I don't know how to do that. Instead, a simple BFS should do it. Intuition was telling me that it could be done in 3M steps (which is very fast), but the initial implementations were leading to TLE. The problem was that I was enqueuing items outside of the [0..1000] range, which was leading to an exponential execution time. With the modification inside the traversal piece, it did the trick. Happy Halloween you all! Code is below, cheers, ACC.

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 = 4
Output: 2
Explanation:
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 = 12
Output: 2
Explanation:
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 = -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 4:

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

Example 5:

```Input: nums = [1], start = 0, goal = 3
Output: 3
Explanation:
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`
• `-109 <= nums[i], goal <= 109`
• `0 <= start <= 1000`
• `start != goal`
• All the integers in `nums` are distinct.
Accepted
3,892
Submissions
9,712

```public class NumQueueItem
{
public long n = 0;
public int numberOfSteps = 0;

public NumQueueItem(long n, int numberOfSteps)
{
this.n = n;
this.numberOfSteps = numberOfSteps;
}
}
public int MinimumOperations(int[] nums, int start, int goal)
{
Queue queue = new Queue();
Hashtable visited = new Hashtable();

NumQueueItem qi = new NumQueueItem((long)start, 0);
queue.Enqueue(qi);

while (queue.Count > 0)  //O(1000)
{
NumQueueItem cqi = queue.Dequeue();

if ((int)cqi.n == goal) return cqi.numberOfSteps;

for (int i = 0; i < nums.Length; i++) //O(1000)
{
long[] candidates = { cqi.n + nums[i], cqi.n - nums[i], cqi.n ^ nums[i] };
foreach (long candidate in candidates) //O(3)
{
if (!visited.ContainsKey(candidate))
{
if ((int)candidate == goal)
{
return cqi.numberOfSteps + 1;
}
else if (candidate >= 0 && candidate <= 1000)
{
NumQueueItem nqi = new NumQueueItem(candidate, cqi.numberOfSteps + 1);
queue.Enqueue(nqi);
}
}
}
}
}

return -1;
}
```