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.
This approach uses the Breadth-First Search algorithm to explore all possible values of x by applying the operations +nums[i], -nums[i], and ^nums[i] repeatedly. BFS is ideal here because it explores nodes layer by layer, which naturally suits finding the minimum number of steps to a target value like the goal. We'll utilize a queue to manage our exploration process and a set to track visited states to avoid redundant work.
The provided Python code leverages BFS using a queue to explore the minimum steps to reach the goal. Starting from x=start, it iteratively applies each possible operation from nums and checks if it results in the goal. It keeps track of visited numbers to avoid redundant calculations, aiming to minimize the operation count.
Time Complexity: O(n * m), where n is the range of possible x values, limited here to ~1000, and m is the length of nums.
Space Complexity: O(n) due to the queue and set used for exploring and storing visited states.
This approach uses a Depth-First Search strategy with backtracking to recursively explore each path for transforming x into goal. We utilize pruning to avoid unnecessary computations by terminating paths that have exceeded a certain depth or revisiting states. This approach might not be as efficient as BFS in terms of finding the minimum path due to its nature.
The Java solution employs DFS with backtracking, exploring all potential transformations from x to goal recursively. It includes pruning by checking if x has been visited or if it is out of bounds, eliminating redundant paths and controlling recursion depth.
Java
JavaScript
Time Complexity: Theoretical worst-case is O(3^m * n), where n is the nums length and recursion depth is effectively limited by DFS.
Space Complexity: O(n + d), where n is for the visited hashmap and d is the recursion depth.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(n * m), where n is the range of possible x values, limited here to ~1000, and m is the length of nums. |
| Depth-First Search (DFS) with Pruning | Time Complexity: Theoretical worst-case is O(3^m * n), where n is the nums length and recursion depth is effectively limited by DFS. |
| Default 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 |
Minimum Operations to Convert Number | BFS | Leetcode Weekly 265 | Hitesh Tripathi • Hitesh Tripathi • 1,521 views views
Watch 9 more video solutions →Practice Minimum Operations to Convert Number with our built-in code editor and test cases.
Practice on FleetCode