Minimum Operations to Convert Number

Med

#1875Time: O(N * M), where N is the range of valid numbers (1001) and M is the length of the `nums` array. In the worst case, we visit each of the N numbers once, and for each, we iterate through M numbers in `nums` to generate new states.Space: O(N), where N is the range of valid numbers (1001). The space is used for the queue and the `visited` array, both of which can store up to N elements.

Algorithms

Breadth-First Search

Data structures

Array

Prompt

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 &rarr; 14 &rarr; 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 &rarr; 3 &rarr; -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
-10⁹ <= nums[i], goal <= 10⁹
0 <= start <= 1000
start != goal
All the integers in nums are distinct.

Approaches

2 approaches with complexity analysis and trade-offs.

This problem can be modeled as finding the shortest path in an unweighted graph. The numbers we can reach are the nodes, and the three operations (+, -, ^) for each number in nums represent the edges. Breadth-First Search (BFS) is the ideal algorithm for finding the shortest path in an unweighted graph because it explores the graph level by level. This guarantees that the first time we reach the goal, it will be through the minimum number of operations.

Algorithm

Create a queue and add the start value.
Create a visited boolean array of size 1001 to keep track of visited numbers in the range [0, 1000]. Mark start as visited.
Initialize an operations counter to 0.
While the queue is not empty, perform a level-order traversal:
- Get the number of elements in the current level (levelSize).
- Increment the operations counter.
- For i from 0 to levelSize - 1:
  - Dequeue the current number x.
  - For each num in the nums array:
    - Calculate the three possible next numbers: next_add = x + num, next_sub = x - num, and next_xor = x ^ num.
    - For each of these next_val:
      - If next_val equals goal, the shortest path is found. Return the current operations count.
      - If next_val is within the range [0, 1000] and has not been visited:
        
        Mark next_val as visited.
        
        Enqueue next_val.
If the queue becomes empty and the goal has not been reached, it is impossible to convert start to goal. Return -1.

Walkthrough

The core of this approach is a systematic, level-by-level exploration of all reachable numbers starting from start. We use a queue to manage the numbers to visit, ensuring a breadth-first traversal. A visited array is crucial to prevent cycles and avoid redundant computations by ensuring each number between 0 and 1000 is processed at most once.

The search begins with the start number at level 0. In each subsequent step (level), we generate all possible numbers that can be reached from the numbers in the current level by applying one of the three operations with every element of nums. If any of these newly generated numbers is the goal, we have found our solution. If a new number is within the valid range [0, 1000] and hasn't been visited, we add it to the queue for future exploration. This process continues until the goal is found or the queue is empty, which signifies that the goal is unreachable.

1import java.util.Queue;2import java.util.LinkedList;3 4class Solution {5    public int minimumOperations(int[] nums, int start, int goal) {6        Queue<Integer> queue = new LinkedList<>();7        boolean[] visited = new boolean[1001];8 9        queue.offer(start);10        visited[start] = true;11 12        int operations = 0;13 14        while (!queue.isEmpty()) {15            int levelSize = queue.size();16            operations++;17 18            for (int i = 0; i < levelSize; i++) {19                int currentX = queue.poll();20 21                for (int num : nums) {22                    // Operation 1: x + num23                    int next1 = currentX + num;24                    if (next1 == goal) {25                        return operations;26                    }27                    if (next1 >= 0 && next1 <= 1000 && !visited[next1]) {28                        visited[next1] = true;29                        queue.offer(next1);30                    }31 32                    // Operation 2: x - num33                    int next2 = currentX - num;34                    if (next2 == goal) {35                        return operations;36                    }37                    if (next2 >= 0 && next2 <= 1000 && !visited[next2]) {38                        visited[next2] = true;39                        queue.offer(next2);40                    }41 42                    // Operation 3: x ^ num43                    int next3 = currentX ^ num;44                    if (next3 == goal) {45                        return operations;46                    }47                    if (next3 >= 0 && next3 <= 1000 && !visited[next3]) {48                        visited[next3] = true;49                        queue.offer(next3);50                    }51                }52            }53        }54 55        return -1;56    }57}

Complexity

Time

O(N * M), where N is the range of valid numbers (1001) and M is the length of the `nums` array. In the worst case, we visit each of the N numbers once, and for each, we iterate through M numbers in `nums` to generate new states.

Space

O(N), where N is the range of valid numbers (1001). The space is used for the queue and the `visited` array, both of which can store up to N elements.

Trade-offs

Pros

Guaranteed to find the minimum number of operations.
Relatively straightforward to implement.
Efficient enough to pass within the given constraints.

Cons

May explore a large number of states if the shortest path is long.
Can be less efficient than a bidirectional search for certain graph structures.

Bidirectional BFS is an optimization of the standard BFS approach. It works by running two simultaneous BFS searches—one forward from the start node and one backward from the goal node. The algorithm terminates when the two search frontiers intersect. By searching from both ends, the total number of explored states can be drastically reduced from O(b^d) to O(2 * b^(d/2)), where b is the branching factor and d is the path length. This makes it much faster, especially for problems with long solution paths.

Algorithm

First, check if goal is within the valid range [0, 1000]. If not, this approach is not applicable, and we should fall back to a standard BFS.
Initialize two queues: q_start with start and q_goal with goal.
Initialize two distance maps (or arrays): dist_start to store distances from start, and dist_goal to store distances from goal. Initialize dist_start[start] = 0 and dist_goal[goal] = 0.
In a loop, as long as both queues are non-empty:
- To keep the search balanced, choose to expand the smaller of the two queues.
- Let's say we expand q_start. Dequeue a node x.
- For each num in nums, generate the three next states (x+num, x-num, x^num).
- For each next_x:
  - Check if next_x has been visited by the backward search (i.e., exists in dist_goal). If so, a meeting point is found. The total operations are dist_start[x] + 1 + dist_goal[next_x]. Return this value.
  - If next_x is valid and not yet in dist_start, add it to q_start and record its distance.
- Perform a similar expansion for q_goal, using the reverse operations.
If the loop terminates because a queue is empty, no path exists. Return -1.

Walkthrough

This approach is only feasible when the operations are reversible and the goal itself is a valid starting point for a search (i.e., within the [0, 1000] range). Fortunately, the given operations are reversible: the reverse of + num is - num, - num is + num, and ^ num is its own inverse.

If the goal is outside the valid range, we cannot start a backward search from it, so we must revert to a standard BFS. Assuming goal is in range, we maintain two queues and two distance maps. In each step, we expand the smaller of the two search frontiers to keep the search balanced. When expanding a node x from the start-search, we check if any of its neighbors have already been visited by the goal-search. If a meeting point is found, we can combine the distances from both searches to get the total minimum operations.

1import java.util.Queue;2import java.util.LinkedList;3import java.util.Map;4import java.util.HashMap;5 6class Solution {7    public int minimumOperations(int[] nums, int start, int goal) {8        // Fallback to standard BFS if goal is out of range for a Bi-BFS starting point.9        if (goal < 0 || goal > 1000) {10            return standardBfs(nums, start, goal);11        }12 13        Queue<Integer> qStart = new LinkedList<>();14        Map<Integer, Integer> distStart = new HashMap<>();15        qStart.offer(start);16        distStart.put(start, 0);17 18        Queue<Integer> qGoal = new LinkedList<>();19        Map<Integer, Integer> distGoal = new HashMap<>();20        qGoal.offer(goal);21        distGoal.put(goal, 0);22 23        int ops = 0;24        while (!qStart.isEmpty() && !qGoal.isEmpty()) {25            ops++;26            // Always expand the smaller queue to keep search balanced27            if (qStart.size() <= qGoal.size()) {28                int result = expandQueue(qStart, distStart, distGoal, nums, ops);29                if (result != -1) return result;30            } else {31                int result = expandQueue(qGoal, distGoal, distStart, nums, ops);32                if (result != -1) return result;33            }34        }35 36        return -1;37    }38 39    private int expandQueue(Queue<Integer> queue, Map<Integer, Integer> dist, Map<Integer, Integer> otherDist, int[] nums, int ops) {40        int levelSize = queue.size();41        for (int i = 0; i < levelSize; i++) {42            int current = queue.poll();43 44            for (int num : nums) {45                int[] nextStates = {current + num, current - num, current ^ num};46 47                for (int next : nextStates) {48                    if (otherDist.containsKey(next)) {49                        return ops + otherDist.get(next);50                    }51                    if (next >= 0 && next <= 1000 && !dist.containsKey(next)) {52                        dist.put(next, ops);53                        queue.offer(next);54                    }55                }56            }57        }58        return -1;59    }60 61    // Standard BFS for fallback when goal is out of bounds62    private int standardBfs(int[] nums, int start, int goal) {63        Queue<Integer> queue = new LinkedList<>();64        boolean[] visited = new boolean[1001];65        if(start >= 0 && start <= 1000) {66            queue.offer(start);67            visited[start] = true;68        }69        int operations = 0;70        while (!queue.isEmpty()) {71            int levelSize = queue.size();72            operations++;73            for (int i = 0; i < levelSize; i++) {74                int currentX = queue.poll();75                for (int num : nums) {76                    int[] nextStates = {currentX + num, currentX - num, currentX ^ num};77                    for (int next : nextStates) {78                        if (next == goal) return operations;79                        if (next >= 0 && next <= 1000 && !visited[next]) {80                            visited[next] = true;81                            queue.offer(next);82                        }83                    }84                }85            }86        }87        return -1;88    }89}

Complexity

Time

O(N * M) in the worst case, same as standard BFS. However, its average-case performance is significantly better at O(M * b^(d/2)), where `b` is the branching factor and `d` is the shortest path length.

Space

O(N), where N is the range of valid numbers (1001). In the worst case, both distance maps could store up to N/2 elements. On average, the space is O(b^(d/2)), which is much better than standard BFS.

Trade-offs

Pros

Potentially much faster than standard BFS by reducing the search space exponentially.
Optimal for finding shortest paths in large graphs where the path length is significant.

Cons

Significantly more complex to implement than a standard BFS.
Only provides a performance benefit if the goal is within the valid range [0, 1000].
Requires more memory to maintain two queues and two distance/visited structures.

Solutions

Solution

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 ; } }

1class 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 ; } };

1class 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 - 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem