Minimum Operations to Convert Number — Editorial

Opening the reading…

Intuitionwhy the numeric operations form a shortest-path problem

Think of every valid intermediate value as a node in a graph. From a value x, each number in nums gives up to three directed edges: x + num, x - num, and x ^ num. The edge represents one operation, so converting start to goal means finding a path whose length is as small as possible.

Only values from 0 through 1000 can be used as the source of another operation. That gives at most 1001 reusable states, regardless of how large the numbers in nums or goal are. A result outside this range is still useful if it equals goal, because the conversion ends there; otherwise it cannot lead to any later operation and can be discarded.

BFS explores all values reachable in zero operations, then all values reachable in one operation, then two, and so on. Therefore, the first time an operation produces goal, its operation count is minimum. A visited array prevents repeated values from producing the same future work again.

Approachturning each operation into one BFS transition

Create a visited array for values 0 through 1000 and put start into a queue with distance 0, because these are the only values that can be expanded and each value needs to be expanded at most once.

Remove one state val and its distance steps from the front of the queue, because BFS processes states in nondecreasing operation count and every transition from this state costs exactly one more operation.

For every num, compute val + num, val - num, and val ^ num, because these are precisely the three results allowed by one choice of nums element.

Check whether each result equals goal before checking its range, because an out-of-range goal is a valid final result even though it cannot be used for another operation.

If a result is in the range 0 through 1000 and has not been visited, mark it immediately and enqueue it with steps + 1, because marking at insertion prevents duplicate queue entries from the same state.

If the queue empties without producing goal, return -1, because every reusable state and every legal transition from it has then been exhausted.

Complexitybounded by the 1001 reusable values

MEASURE	BOUND	WHY
Time	O(1001 x n)	There are at most 1001 reusable states, and each is removed from the queue once. Removing one state examines three results for each of the n numbers, so no state-number pair is processed more than once.
Space	O(1001)	The visited array has 1001 entries and the queue can contain at most one entry for each visited reusable value. This is extra space; the returned integer is required output and contributes nothing. In the worst input shape, all 1001 valid values are reached and queued.

Here n is nums.length. The value range contributes the fixed factor 1001, and the returned integer uses no output storage.

Annotated solutionC++ · iterative BFS · bounded integer state space

CPPBFS over reusable values, with the goal check before the range check.

#include <vector>
#include <queue>
#include <utility>

using namespace std;

class Solution {
public:
    int minimumOperations(vector<int>& nums, int start, int goal) {
        vector<bool> visited(1001, false);
        queue<pair<int, int>> q;

        q.push({start, 0});
        visited[start] = true;

        while (!q.empty()) {
            auto [val, steps] = q.front();
            q.pop();

            for (int num : nums) {
                int next[3] = {val + num, val - num, val ^ num};

                for (int candidate : next) {
                    if (candidate == goal) {
                        return steps + 1;
                    }

                    if (candidate >= 0 && candidate <= 1000 &&
                        !visited[candidate]) {
                        visited[candidate] = true;
                        q.push({candidate, steps + 1});
                    }
                }
            }
        }

        return -1;
    }
};

The ordering of the two checks is the key detail. candidate == goal must come first, since the statement permits the final operation to leave the range. Only after ruling out an immediate success do you ask whether the result can be expanded later and whether it has already been visited.

Marking a value visited when you enqueue it, rather than when you dequeue it, keeps the queue compact. Several different parent states may generate the same candidate during one or nearby BFS layers; the first insertion already gives that candidate its shortest distance, so later insertions add no information.