Skip to main content
Talentd

Minimum Operations to Convert Number - Solution & Explanation

MediumArrayBreadth-First Search11 min readAsked at: Google
Practice this problem

Problem Statement

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 <= 109
  • 0 <= start <= 1000
  • start != goal
  • All the integers in nums are distinct.

Approach Overview

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 1: Breadth-First Search (BFS) 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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) with Pruning

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) due to the queue and set used for exploring and storing visited states.

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.
Space Complexity: O(n + d), where n is for the visited hashmap and d is the recursion depth.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Breadth-First Search (BFS)O(n * 1000)O(1000)Best for shortest-path problems in an unweighted state graph
DFS with PruningO(n * 1000) worst caseO(1000)Useful for exploring paths recursively when pruning limits the search space

Video Solution

Minimum Operations to Convert Number | BFS | Leetcode Weekly 265 | Hitesh Tripathi • Hitesh Tripathi • 1,540 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Convert Number easy or hard?
Minimum Operations to Convert Number is generally classified as a medium difficulty problem. The operations themselves are simple, but recognizing that the problem forms a graph and applying BFS to compute the shortest sequence of operations requires algorithmic insight.
Minimum Operations to Convert Number Python/Java solution
Most solutions implement BFS using a queue (collections.deque in Python or Queue in Java). For every number dequeued, iterate through nums and compute x + num, x - num, and x ^ num. If the result equals the goal, return the current step count plus one.
How to solve Minimum Operations to Convert Number in O(n)?
The practical optimal solution uses BFS with a bounded state space rather than strict O(n). Each number from 0 to 1000 is visited at most once, and for every visit the algorithm iterates through nums and applies +, -, and XOR operations. This results in O(n * 1000) time with O(1000) space.
What is the best approach for Minimum Operations to Convert Number?
Breadth-First Search (BFS) is the best approach because the problem asks for the minimum number of operations. BFS explores states level by level, guaranteeing the first time the goal is reached is the shortest path. The search space is limited to numbers between 0 and 1000, making BFS efficient.
Is Minimum Operations to Convert Number asked at Google/Amazon/Meta?
Graph traversal and BFS state-search problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The problem tests your ability to model numeric transformations as a graph and apply BFS for shortest paths.
What data structure is used in Minimum Operations to Convert Number?
The core data structure is a queue used in Breadth-First Search. A visited set or boolean array tracks numbers already explored in the range 0 to 1000 to prevent cycles. The nums array provides the operation values used to generate new states.
What is the time complexity of Minimum Operations to Convert Number?
The BFS solution runs in O(n * 1000) time where n is the length of the nums array. Each valid state between 0 and 1000 can be processed once, and for each state you try three operations with every number in nums. Space complexity is O(1000) for the queue and visited set.

Ready to solve this problem?

Practice Minimum Operations to Convert Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Reduce X to Zero