2059. Minimum Operations to Convert Number LeetCode Solution
In this guide, you will get 2059. Minimum Operations to Convert Number LeetCode Solution with the best time and space complexity. The solution to Minimum Operations to Convert Number problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Minimum Operations to Convert Number
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
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.
Complexity Analysis
Time Complexity: O(1000n)
Space Complexity: O(1000)
2059. Minimum Operations to Convert Number LeetCode Solution in C++
class Solution {
public:
int minimumOperations(vector<int>& nums, int start, int goal) {
queue<int> q{{start}};
vector<bool> seen(1001);
seen[start] = true;
for (int step = 1; !q.empty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
const int x = q.front();
q.pop();
for (const int num : nums) {
for (const int res : {x + num, x - num, x ^ num}) {
if (res == goal)
return step;
if (res < 0 || res > 1000 || seen[res])
continue;
seen[res] = true;
q.push(res);
}
}
}
return -1;
}
}; /* code provided by PROGIEZ */
2059. Minimum Operations to Convert Number LeetCode Solution in Java
class Solution {
public int minimumOperations(int[] nums, int start, int goal) {
Queue<Integer> q = new ArrayDeque<>(List.of(start));
boolean[] seen = new boolean[1001];
seen[start] = true;
for (int step = 1; !q.isEmpty(); ++step)
for (int sz = q.size(); sz > 0; --sz) {
final int x = q.poll();
for (final int num : nums) {
for (final int res : new int[] {x + num, x - num, x ^ num}) {
if (res == goal)
return step;
if (res < 0 || res > 1000 || seen[res])
continue;
seen[res] = true;
q.offer(res);
}
}
}
return -1;
}
} // code provided by PROGIEZ
2059. Minimum Operations to Convert Number LeetCode Solution in Python
class Solution:
def minimumOperations(self, nums: list[int], start: int, goal: int) -> int:
q = collections.deque([start])
seen = {start}
step = 1
while q:
for _ in range(len(q)):
x = q.popleft()
for num in nums:
for res in (x + num, x - num, x ^ num):
if res == goal:
return step
if res < 0 or res > 1000 or res in seen:
continue
seen.add(res)
q.append(res)
step += 1
return -1 # code by PROGIEZ
