Watch 10 video solutions for Minimum Operations to Convert Number, a medium level problem involving Array, Breadth-First Search. This walkthrough by Hitesh Tripathi has 1,521 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 != goalnums are distinct.Problem Overview: You start with an integer start and want to reach goal. In one operation, pick any value from nums and apply + num, - num, or ^ num (bitwise XOR). Values can temporarily go outside the valid range, but only numbers between 0 and 1000 can continue generating new states. The task is to return the minimum number of operations needed to reach goal.
Approach 1: Breadth-First Search (BFS) (Time: O(n * 1000), Space: O(1000))
This problem naturally forms a graph where each integer value is a node and each operation generates edges to new nodes. Starting from start, run Breadth-First Search to explore all reachable numbers level by level. For each value dequeued, iterate through nums and compute the three possible results: x + num, x - num, and x ^ num. If any operation directly produces goal, return the current step count + 1. Maintain a visited set for values in the valid range [0,1000] to avoid cycles. BFS guarantees the first time you reach the goal is the minimum number of operations. This approach uses a queue and state expansion typical in Breadth-First Search problems.
Approach 2: Depth-First Search (DFS) with Pruning (Time: O(n * 1000) worst case, Space: O(1000))
DFS explores operation sequences recursively while tracking visited states. From the current value, recursively apply the three operations with each element in nums. To prevent exponential explosion, prune branches when the value falls outside the valid range or has already been visited with fewer steps. A memo or visited structure ensures each number between 0 and 1000 is processed only once at an optimal depth. Although DFS can find a valid path, it requires careful pruning and still may explore deeper paths before discovering the shortest one.
The transitions rely heavily on iterating through the nums array and generating new states. The bounded range of 0..1000 keeps the search space manageable and makes graph traversal practical.
Recommended for interviews: The BFS approach is the expected solution. It models the problem as an unweighted shortest path search and guarantees the minimum number of operations. Interviewers typically look for recognizing the implicit graph and applying BFS with a visited set. DFS with pruning works but is harder to reason about for shortest paths and is usually considered a secondary approach.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n * 1000) | O(1000) | Best for shortest-path problems in an unweighted state graph |
| DFS with Pruning | O(n * 1000) worst case | O(1000) | Useful for exploring paths recursively when pruning limits the search space |