Minimum Operations to Convert Number

Problem

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 _theminimum number of operations needed to convert _x = start intogoal , and-1 if it is not possible.

Examples

Example 1

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 2

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 3

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

Constraints

• 1 <= nums.length <= 1000
• -10^9 <= nums[i], goal <= 10^9
• 0 <= start <= 1000
• start != goal
• All the integers in nums are distinct.

Solution

Method 1 – Breadth-First Search (BFS)

Intuition

We want the minimum number of operations to reach goal from start using allowed operations. BFS explores all possible states in increasing order of steps, ensuring the shortest path is found.

Approach

1. Use a queue to perform BFS starting from start.
2. For each value, try all three operations (+, -, ^) with each nums[i].
3. If the result is goal, return the number of steps.
4. If the result is in [0, 1000] and not visited, add to queue and mark visited.
5. If the result is out of bounds, only check if it matches goal.
6. If queue is empty and goal not reached, return -1.

Code

C++

#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minimumOperations(vector<int>& nums, int start, int goal) {
        queue<pair<int, int>> q;
        vector<bool> vis(1001, false);
        q.push({start, 0});
        vis[start] = true;
        while (!q.empty()) {
            auto [x, step] = q.front(); q.pop();
            for (int v : nums) {
                for (int y : {x + v, x - v, x ^ v}) {
                    if (y == goal) return step + 1;
                    if (0 <= y && y <= 1000 && !vis[y]) {
                        vis[y] = true;
                        q.push({y, step + 1});
                    }
                }
            }
        }
        return -1;
    }
};

Go

func minimumOperations(nums []int, start int, goal int) int {
    vis := make([]bool, 1001)
    type pair struct{ x, step int }
    q := []pair{{start, 0}}
    vis[start] = true
    for len(q) > 0 {
        p := q[0]
        q = q[1:]
        for _, v := range nums {
            for _, y := range []int{p.x + v, p.x - v, p.x ^ v} {
                if y == goal {
                    return p.step + 1
                }
                if 0 <= y && y <= 1000 && !vis[y] {
                    vis[y] = true
                    q = append(q, pair{y, p.step + 1})
                }
            }
        }
    }
    return -1
}

Java

import java.util.*;
class Solution {
    public int minimumOperations(int[] nums, int start, int goal) {
        Queue<int[]> q = new LinkedList<>();
        boolean[] vis = new boolean[1001];
        q.add(new int[]{start, 0});
        vis[start] = true;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int x = p[0], step = p[1];
            for (int v : nums) {
                for (int y : new int[]{x + v, x - v, x ^ v}) {
                    if (y == goal) return step + 1;
                    if (0 <= y && y <= 1000 && !vis[y]) {
                        vis[y] = true;
                        q.add(new int[]{y, step + 1});
                    }
                }
            }
        }
        return -1;
    }
}

Kotlin

import java.util.LinkedList
class Solution {
    fun minimumOperations(nums: IntArray, start: Int, goal: Int): Int {
        val vis = BooleanArray(1001)
        val q = LinkedList<Pair<Int, Int>>()
        q.add(start to 0)
        vis[start] = true
        while (q.isNotEmpty()) {
            val (x, step) = q.poll()
            for (v in nums) {
                for (y in listOf(x + v, x - v, x xor v)) {
                    if (y == goal) return step + 1
                    if (y in 0..1000 && !vis[y]) {
                        vis[y] = true
                        q.add(y to step + 1)
                    }
                }
            }
        }
        return -1
    }
}

Python

from collections import deque
class Solution:
    def minimumOperations(self, nums: list[int], start: int, goal: int) -> int:
        vis = [False] * 1001
        q = deque([(start, 0)])
        vis[start] = True
        while q:
            x, step = q.popleft()
            for v in nums:
                for y in (x + v, x - v, x ^ v):
                    if y == goal:
                        return step + 1
                    if 0 <= y <= 1000 and not vis[y]:
                        vis[y] = True
                        q.append((y, step + 1))
        return -1

Rust

use std::collections::VecDeque;
impl Solution {
    pub fn minimum_operations(nums: Vec<i32>, start: i32, goal: i32) -> i32 {
        let mut vis = vec![false; 1001];
        let mut q = VecDeque::new();
        q.push_back((start, 0));
        vis[start as usize] = true;
        while let Some((x, step)) = q.pop_front() {
            for &v in &nums {
                for y in [x + v, x - v, x ^ v] {
                    if y == goal {
                        return step + 1;
                    }
                    if 0 <= y && y <= 1000 && !vis[y as usize] {
                        vis[y as usize] = true;
                        q.push_back((y, step + 1));
                    }
                }
            }
        }
        -1
    }
}

TypeScript

class Solution {
    minimumOperations(nums: number[], start: number, goal: number): number {
        const vis = Array(1001).fill(false);
        let q: [number, number][] = [[start, 0]];
        vis[start] = true;
        while (q.length) {
            const [x, step] = q.shift()!;
            for (const v of nums) {
                for (const y of [x + v, x - v, x ^ v]) {
                    if (y === goal) return step + 1;
                    if (0 <= y && y <= 1000 && !vis[y]) {
                        vis[y] = true;
                        q.push([y, step + 1]);
                    }
                }
            }
        }
        return -1;
    }
}

Complexity

• ⏰ Time complexity: O(n * 1000) — Each value in [0,1000] is visited at most once, and for each, we try n operations.
• 🧺 Space complexity: O(1000) — For the visited array and queue.