LeetCode 2059. Minimum Operations to Convert Number Solution in Java, C++, Python & More | Explanation + Code

Description

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 = [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
• -109 <= nums[i], goal <= 109
• 0 <= start <= 1000
• start != goal
• All the integers in nums are distinct.

Solutions

Solution 1

PythonJavaC++GoTypeScript

class Solution: def minimumOperations(self, nums: List[int], start: int, goal: int) -> int: op1 = lambda x, y: x + y op2 = lambda x, y: x - y op3 = lambda x, y: x ^ y ops = [op1, op2, op3] vis = [False] * 1001 q = deque([(start, 0)]) while q: x, step = q.popleft() for num in nums: for op in ops: nx = op(x, num) if nx == goal: return step + 1 if 0 <= nx <= 1000 and not vis[nx]: q.append((nx, step + 1)) vis[nx] = True return -1(code-box)

class Solution { public int minimumOperations(int[] nums, int start, int goal) { IntBinaryOperator op1 = (x, y) -> x + y; IntBinaryOperator op2 = (x, y) -> x - y; IntBinaryOperator op3 = (x, y) -> x ^ y; IntBinaryOperator[] ops = {op1, op2, op3}; boolean[] vis = new boolean[1001]; Queue<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {start, 0}); while (!queue.isEmpty()) { int[] p = queue.poll(); int x = p[0], step = p[1]; for (int num : nums) { for (IntBinaryOperator op : ops) { int nx = op.applyAsInt(x, num); if (nx == goal) { return step + 1; } if (nx >= 0 && nx <= 1000 && !vis[nx]) { queue.offer(new int[] {nx, step + 1}); vis[nx] = true; } } } } return -1; } }(code-box)

class Solution { public: int minimumOperations(vector<int>& nums, int start, int goal) { using pii = pair<int, int>; vector<function<int(int, int)>> ops{ [](int x, int y) { return x + y; }, [](int x, int y) { return x - y; }, [](int x, int y) { return x ^ y; }, }; vector<bool> vis(1001, false); queue<pii> q; q.push({start, 0}); while (!q.empty()) { auto [x, step] = q.front(); q.pop(); for (int num : nums) { for (auto op : ops) { int nx = op(x, num); if (nx == goal) { return step + 1; } if (nx >= 0 && nx <= 1000 && !vis[nx]) { q.push({nx, step + 1}); vis[nx] = true; } } } } return -1; } };(code-box)

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

function minimumOperations(nums: number[], start: number, goal: number): number { const n = nums.length; const op1 = function (x: number, y: number): number { return x + y; }; const op2 = function (x: number, y: number): number { return x - y; }; const op3 = function (x: number, y: number): number { return x ^ y; }; const ops = [op1, op2, op3]; let vis = new Array(1001).fill(false); let quenue: Array<Array<number>> = [[start, 0]]; vis[start] = true; while (quenue.length) { let [x, step] = quenue.shift(); for (let i = 0; i < n; i++) { for (let j = 0; j < ops.length; j++) { const nx = ops[j](x, nums[i]); if (nx == goal) { return step + 1; } if (nx >= 0 && nx <= 1000 && !vis[nx]) { vis[nx] = true; quenue.push([nx, step + 1]); } } } } return -1; }(code-box)

Solution 2

PythonJavaC++Go

class Solution: def minimumOperations(self, nums: List[int], start: int, goal: int) -> int: def next(x): res = [] for num in nums: res.append(x + num) res.append(x - num) res.append(x ^ num) return res q = deque([start]) vis = {start} ans = 0 while q: ans += 1 for _ in range(len(q)): x = q.popleft() for y in next(x): if y == goal: return ans if 0 <= y <= 1000 and y not in vis: vis.add(y) q.append(y) return -1(code-box)

class Solution { public int minimumOperations(int[] nums, int start, int goal) { Deque<Integer> q = new ArrayDeque<>(); q.offer(start); boolean[] vis = new boolean[1001]; int ans = 0; while (!q.isEmpty()) { ++ans; for (int n = q.size(); n > 0; --n) { int x = q.poll(); for (int y : next(nums, x)) { if (y == goal) { return ans; } if (y >= 0 && y <= 1000 && !vis[y]) { vis[y] = true; q.offer(y); } } } } return -1; } private List<Integer> next(int[] nums, int x) { List<Integer> res = new ArrayList<>(); for (int num : nums) { res.add(x + num); res.add(x - num); res.add(x ^ num); } return res; } }(code-box)

class Solution { public: int minimumOperations(vector<int>& nums, int start, int goal) { queue<int> q{{start}}; vector<bool> vis(1001); int ans = 0; while (!q.empty()) { ++ans; for (int n = q.size(); n > 0; --n) { int x = q.front(); q.pop(); for (int y : next(nums, x)) { if (y == goal) return ans; if (y >= 0 && y <= 1000 && !vis[y]) { vis[y] = true; q.push(y); } } } } return -1; } vector<int> next(vector<int>& nums, int x) { vector<int> res; for (int num : nums) { res.push_back(x + num); res.push_back(x - num); res.push_back(x ^ num); } return res; } };(code-box)

func minimumOperations(nums []int, start int, goal int) int { next := func(x int) []int { var res []int for _, num := range nums { res = append(res, []int{x + num, x - num, x ^ num}...) } return res } q := []int{start} vis := make([]bool, 1001) ans := 0 for len(q) > 0 { ans++ for n := len(q); n > 0; n-- { x := q[0] q = q[1:] for _, y := range next(x) { if y == goal { return ans } if y >= 0 && y <= 1000 && !vis[y] { vis[y] = true q = append(q, y) } } } } return -1 }(code-box)

Solution 3

PythonJavaC++Go

class Solution: def minimumOperations(self, nums: List[int], start: int, goal: int) -> int: def next(x): res = [] for num in nums: res.append(x + num) res.append(x - num) res.append(x ^ num) return res def extend(m1, m2, q): for _ in range(len(q)): x = q.popleft() step = m1[x] for y in next(x): if y in m1: continue if y in m2: return step + 1 + m2[y] if 0 <= y <= 1000: m1[y] = step + 1 q.append(y) return -1 m1, m2 = {start: 0}, {goal: 0} q1, q2 = deque([start]), deque([goal]) while q1 and q2: t = extend(m1, m2, q1) if len(q1) <= len(q2) else extend(m2, m1, q2) if t != -1: return t return -1(code-box)

class Solution { private int[] nums; public int minimumOperations(int[] nums, int start, int goal) { this.nums = nums; Map<Integer, Integer> m1 = new HashMap<>(); Map<Integer, Integer> m2 = new HashMap<>(); Deque<Integer> q1 = new ArrayDeque<>(); Deque<Integer> q2 = new ArrayDeque<>(); m1.put(start, 0); m2.put(goal, 0); q1.offer(start); q2.offer(goal); while (!q1.isEmpty() && !q2.isEmpty()) { int t = q1.size() <= q2.size() ? extend(m1, m2, q1) : extend(m2, m1, q2); if (t != -1) { return t; } } return -1; } private int extend(Map<Integer, Integer> m1, Map<Integer, Integer> m2, Deque<Integer> q) { for (int i = q.size(); i > 0; --i) { int x = q.poll(); int step = m1.get(x); for (int y : next(x)) { if (m1.containsKey(y)) { continue; } if (m2.containsKey(y)) { return step + 1 + m2.get(y); } if (y >= 0 && y <= 1000) { m1.put(y, step + 1); q.offer(y); } } } return -1; } private List<Integer> next(int x) { List<Integer> res = new ArrayList<>(); for (int num : nums) { res.add(x + num); res.add(x - num); res.add(x ^ num); } return res; } }(code-box)

class Solution { public: int minimumOperations(vector<int>& nums, int start, int goal) { unordered_map<int, int> m1; unordered_map<int, int> m2; m1[start] = 0; m2[goal] = 0; queue<int> q1{{start}}; queue<int> q2{{goal}}; while (!q1.empty() && !q2.empty()) { int t = q1.size() <= q2.size() ? extend(m1, m2, q1, nums) : extend(m2, m1, q2, nums); if (t != -1) return t; } return -1; } int extend(unordered_map<int, int>& m1, unordered_map<int, int>& m2, queue<int>& q, vector<int>& nums) { for (int i = q.size(); i > 0; --i) { int x = q.front(); int step = m1[x]; q.pop(); for (int y : next(nums, x)) { if (m1.count(y)) continue; if (m2.count(y)) return step + 1 + m2[y]; if (y >= 0 && y <= 1000) { m1[y] = step + 1; q.push(y); } } } return -1; } vector<int> next(vector<int>& nums, int x) { vector<int> res; for (int num : nums) { res.push_back(x + num); res.push_back(x - num); res.push_back(x ^ num); } return res; } };(code-box)

func minimumOperations(nums []int, start int, goal int) int { next := func(x int) []int { var res []int for _, num := range nums { res = append(res, []int{x + num, x - num, x ^ num}...) } return res } m1, m2 := map[int]int{start: 0}, map[int]int{goal: 0} q1, q2 := []int{start}, []int{goal} extend := func() int { for i := len(q1); i > 0; i-- { x := q1[0] q1 = q1[1:] step, _ := m1[x] for _, y := range next(x) { if _, ok := m1[y]; ok { continue } if v, ok := m2[y]; ok { return step + 1 + v } if y >= 0 && y <= 1000 { m1[y] = step + 1 q1 = append(q1, y) } } } return -1 } for len(q1) > 0 && len(q2) > 0 { if len(q1) > len(q2) { m1, m2 = m2, m1 q1, q2 = q2, q1 } t := extend() if t != -1 { return t } } return -1 }(code-box)