Medium
Minimum Operations to Convert Number — C++
Full explanation · Time O(m * n) · Space O(m)
// Time: O(n * m), m is max x
// Space: O(m)
class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
static const int MAX_X = 1000;
vector<int> new_nums;
for (const auto& y : nums) {
if (y && ((0 <= y && y <= MAX_X) || (0 <= (goal - y) && (goal - y) <= MAX_X) || (0 <= (goal + y) && (goal + y) <= MAX_X) || (0 <= (goal ^ y) && (goal ^ y) <= MAX_X))) {
new_nums.emplace_back(y);
}
}
nums = move(new_nums);
vector<pair<int, int>> q = {{start, 0}};
unordered_set<int> lookup = {start};
while (!empty(q)) {
vector<pair<int, int>> new_q;
for (const auto& [x, steps] : q) {
for (const auto& y : nums) {
for (const auto& nx : {x + y, x - y, x ^ y}) {
if (nx == goal) {
return steps + 1;
}
if (!(0 <= nx && nx <= MAX_X) || lookup.count(nx)) {
continue;
}
lookup.emplace(nx);
new_q.emplace_back(nx, steps + 1);
}
}
}
q = move(new_q);
}
return -1;
}
};