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.

Minimum Operations to Convert Number - LeetCode

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);
    visited.Add(qi.n, true);

    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);
                        visited.Add(nqi.n, true);
                    }
                }
            }
        }
    }

    return -1;
}