| comments | difficulty | edit_url | rating | source | tags | ||
|---|---|---|---|---|---|---|---|
true |
Medium |
1849 |
Weekly Contest 265 Q3 |
|
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 <= 1090 <= start <= 1000start != goal- All the integers in
numsare distinct.
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 -1class 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;
}
}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;
}
};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
}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;
}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 -1class 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;
}
}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;
}
};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
}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 -1class 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;
}
}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;
}
};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
}