Minimum Operations to Convert Number
Problem
Start at integer start; in one operation pick x in nums and replace the current value y with y+x, y-x, or y XOR x. Values outside [0, 1000] are illegal. Return the fewest operations to reach goal, or -1.
nums = [2, 4, 12], start = 2, goal = 122from collections import deque
def minimum_operations(nums, start, goal):
seen = {start}
q = deque([(start, 0)])
while q:
y, d = q.popleft()
for x in nums:
for ny in (y + x, y - x, y ^ x):
if ny == goal:
return d + 1
if 0 <= ny <= 1000 and ny not in seen:
seen.add(ny)
q.append((ny, d + 1))
return -1function minimumOperations(nums, start, goal) {
const seen = new Set([start]);
const q = [[start, 0]];
while (q.length) {
const [y, d] = q.shift();
for (const x of nums) {
for (const ny of [y + x, y - x, y ^ x]) {
if (ny === goal) return d + 1;
if (ny >= 0 && ny <= 1000 && !seen.has(ny)) {
seen.add(ny);
q.push([ny, d + 1]);
}
}
}
}
return -1;
}class Solution {
public int minimumOperations(int[] nums, int start, int goal) {
java.util.Set<Integer> seen = new java.util.HashSet<>();
seen.add(start);
java.util.Deque<int[]> q = new java.util.ArrayDeque<>();
q.offer(new int[]{ start, 0 });
while (!q.isEmpty()) {
int[] cur = q.poll();
int y = cur[0], d = cur[1];
for (int x : nums) {
int[] cands = { y + x, y - x, y ^ x };
for (int ny : cands) {
if (ny == goal) return d + 1;
if (ny >= 0 && ny <= 1000 && seen.add(ny)) q.offer(new int[]{ ny, d + 1 });
}
}
}
return -1;
}
}int minimumOperations(vector<int>& nums, int start, int goal) {
unordered_set<int> seen{ start };
queue<pair<int, int>> q;
q.push({ start, 0 });
while (!q.empty()) {
auto [y, d] = q.front(); q.pop();
for (int x : nums) {
for (int ny : { y + x, y - x, y ^ x }) {
if (ny == goal) return d + 1;
if (ny >= 0 && ny <= 1000 && !seen.count(ny)) {
seen.insert(ny);
q.push({ ny, d + 1 });
}
}
}
}
return -1;
}Explanation
Think of every reachable number as a node and every allowed operation as an edge that costs one step. Since all steps cost the same, "fewest operations" is a shortest-path-by-steps question, which is exactly what BFS answers.
We start a queue at (start, 0) and a seen set so we never process the same value twice. Popping a value y at depth d, we try every x in nums and form three candidates: y + x, y - x, and y ^ x (bitwise XOR).
For each candidate ny: if it equals goal, we immediately return d + 1 — because BFS explores in waves of increasing depth, this is guaranteed to be the minimum. Otherwise, only values inside the legal range 0 <= ny <= 1000 and not already seen get enqueued; everything else is illegal or already handled.
Example: nums = [2, 4, 12], start = 2, goal = 12. From 2 we reach 2 ^ 12 = 14 (depth 1); from 14 we reach 14 - 2 = 12, the goal, at depth 2, so the answer is 2.
If the queue empties without ever hitting the goal, no sequence of operations works and we return -1.