2059. Minimum Operations to Convert Number
Problem Description
In this problem, we are provided with an array nums
containing distinct integers and two other integers: start
and goal
. Our objective is to transform the value of a variable x
from start
to goal
. The variable x
can be modified by repeatedly performing the following operations:
- Adding any number
nums[i]
tox
(x + nums[i]
) - Subtracting any number
nums[i]
fromx
(x - nums[i]
) - Performing a bitwise-XOR between
x
and any numbernums[i]
(x ^ nums[i]
)
We are allowed to use each element in nums
repeatedly in any order. The range of permissible values for x
during the operations is from 0
to 1000
, inclusive. If an operation results in x
falling outside this range, no further operations can be applied, although reaching an out-of-range number does not necessarily mean failing to reach the goalāit's possible that the goal, too, is out of range.
Our task is to find the minimum number of operations required to turn x
from start
to goal
or to determine that such a transformation is impossible, in which case we would return -1
.
Flowchart Walkthrough
Let's analyze the problem using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The operations to convert one number to another can be represented as nodes and edges in a graph, where each number is a node and each valid operation forms an edge to another node.
Is it a tree?
- No: The connections between numbers aren't hierarchical and may form cycles, so it's not a tree structure.
Is the problem related to directed acyclic graphs (DAGs)?
- No: While there's directionality in operations (you can't undo an operation), the main concern is not about DAG properties such as topological sorting.
Is the problem related to shortest paths?
- Yes: The goal is to find the minimum number of operations to convert one number to another, which is akin to finding the shortest path in a graph from a source node to a target node.
Is the graph weighted?
- No: Each operation (edge) represents a single step, so each edge has the same weight.
Conclusion: The flowchart suggests using BFS for this unweighted shortest path problem, as BFS is optimal for finding the shortest path in an unweighted graph.
Intuition
To find the minimum number of operations to reach the goal, we can use Breadth-First Search (BFS). BFS is a suitable approach since we want to find the shortest pathāhere, the smallest number of operationsāto transform start
into goal
. BFS ensures that we explore all possibilities generated by the three operations (addition, subtraction, and XOR) level by level. By visiting each "level" sequentially, we guarantee that the first time we reach the goal
, it is the minimum number of steps taken.
The BFS algorithm starts with start
, applying all possible operations while maintaining a queue. Each element in the queue is a pair: the resulting number after applying an operation and the count of operations performed to reach that number. We mark each visited number within the range of 0
to 1000
to prevent re-visiting the same number multiple times and getting into infinite loops.
Whenever any operation results in the goal
, we immediately return the current step count plus one. If the queue is exhausted without finding the goal
, we conclude it is not possible to reach the goal
with the given operations and return -1
.
The algorithm effectively explores different pathways of reaching goal
from start
while avoiding duplicate work, thus efficiently finding the minimum steps required.
Learn more about Breadth-First Search patterns.
Solution Approach
The provided solution in Python makes use of the Breadth-First Search (BFS) algorithm. This solution first defines three operations as lambdas that take two arguments x
and y
and return x + y
, x - y
, and x ^ y
respectively. These lambdas represent the three permissible operations on x
as described in the problem statement.
The BFS algorithm is implemented as follows:
-
A boolean visited array
vis
of size1001
is used to keep track of numbers in the range0
to1000
that have already been explored. Initially, all values are set toFalse
since no numbers have been explored. -
A queue
q
is initiated with a tuple containing thestart
number and step counter set to0
. The Python deque (double-ended queue) is chosen for efficiency since we need to add and remove elements from both ends. -
The BFS starts by popping elements from the queue one by one. For each number
x
dequeued along with its associated step count, we:- Iterate over each number
num
innums
. - For each number
num
, we apply the three operations using the previously defined lambdas. The result of each operation is stored innx
.
- Iterate over each number
-
For each result
nx
, we check ifnx
equals thegoal
. If it does, we have found the shortest path togoal
and return the current step count plus one, because we have made another operation to reachgoal
. -
If
nx
is within the bounds (0 <= nx <= 1000
) and has not been visited before, we add(nx, step + 1)
to the queue and marknx
as visited. -
If the queue is emptied and
goal
has not been found, this implies that it is not possible to convertstart
intogoal
with the provided operations, and we return-1
.
The BFS continues to work level by level, guaranteeing that each number is reached in the minimum number of operations, and when goal
is reached, it is done with the least number of transformations possible.
This algorithm makes efficient use of both time and space by avoiding unnecessary recomputation and by managing the search space with the visited array and the queue for pending computations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution with a small example:
Assume nums = [2, 3]
, start = 0
, and goal = 10
.
-
We begin by initiating the BFS process with the starting point. Our queue
q
=[(0, 0)]
, where0
is the initial value ofx
and0
is the step counter. The visited arrayvis
is set toFalse
for all values. -
The BFS starts by dequeuing the first element
(0, 0)
fromq
. We perform all three operations onx
with each number innums
. -
After applying the operations (add, subtract, XOR) with
num = 2
, we get three possibilities:x + 2 = 2
,x - 2 = -2
, andx ^ 2 = 2
. The second result is out of bounds, so only 2 will be queued:q = [(2, 1)]
.Repeating with
num = 3
, we getx + 3 = 3
,x - 3 = -3
, andx ^ 3 = 3
. Again, "-3" is out of bounds, and since3
is not yet visited, we add it to the queue. Nowq = [(2, 1), (3, 1)]
. -
Next, we dequeue
(2, 1)
and repeat the operations with allnums
:With
num = 2
, we get2 + 2 = 4
,2 - 2 = 0
(already visited), and2 ^ 2 = 0
(already visited).With
num = 3
, we get2 + 3 = 5
,2 - 3 = -1
(out of bounds), and2 ^ 3 = 1
. The new numbers4
and1
are added to the queue, while0
is ignored. Now,q = [(3, 1), (4, 2), (1, 2)]
. -
This process continues as we dequeue from
q
, apply operations, and enqueue non-visited results until we either achieve thegoal
of10
or empty the queue.After more iterations, we might eventually reach a state where
q
includes(10, N)
, whereN
is the number of operations taken. At this point, we returnN + 1
because we have performed one more operation to reach our goal.
If we never reach the value of 10
, and we have no more elements left in our queue to explore, we will return -1
, signifying it's not possible to reach the goal from the start given the operations.
Through this approach, we ensure that we always take the shortest path since BFS explores all possibilities one step at a time and does not revisit any number we've seen before.
Solution Implementation
1from collections import deque
2from typing import List
3
4class Solution:
5 def minimum_operations(self, nums: List[int], start: int, goal: int) -> int:
6 # Define the possible operations using operator lambdas
7 add = lambda x, y: x + y
8 subtract = lambda x, y: x - y
9 xor = lambda x, y: x ^ y
10 operations = [add, subtract, xor] # Store operations in a list for easy iteration
11
12 # Create an array to keep track of visited states
13 visited = [False] * 1001
14
15 # Initialize queue with a tuple containing the starting value and initial step count of 0
16 queue = deque([(start, 0)])
17
18 # Run a BFS to explore all possible states
19 while queue:
20 current_value, step_count = queue.popleft() # Dequeue the next state to process
21
22 # Iterate over each number in the given array
23 for num in nums:
24 # Try all three operations with the current number and value dequeued
25 for operation in operations:
26 next_value = operation(current_value, num)
27 # Check if we have reached the goal
28 if next_value == goal:
29 return step_count + 1
30 # Enqueue the next state if it is valid and hasn't been visited
31 if 0 <= next_value <= 1000 and not visited[next_value]:
32 queue.append((next_value, step_count + 1))
33 visited[next_value] = True
34
35 # Return -1 if the goal is not reachable with the given operations and constraints
36 return -1
37
38# Example usage:
39# solution = Solution()
40# result = solution.minimum_operations([1,3],[2],[4])
41# print("Minimum operations to reach the goal:", result)
42
1import java.util.ArrayDeque;
2import java.util.Queue;
3import java.util.function.IntBinaryOperator;
4
5class Solution {
6 public int minimumOperations(int[] nums, int start, int goal) {
7 // IntBinaryOperator is a functional interface representing an operation upon two int-valued operands
8 // and returning an int-valued result. Here, we define three operations: addition, subtraction, and bitwise XOR.
9 IntBinaryOperator add = (x, y) -> x + y;
10 IntBinaryOperator subtract = (x, y) -> x - y;
11 IntBinaryOperator bitwiseXor = (x, y) -> x ^ y;
12
13 // Array of the operations
14 IntBinaryOperator[] operations = {add, subtract, bitwiseXor};
15
16 // A boolean array to keep track of visited values
17 boolean[] visited = new boolean[1001];
18
19 // Queue to manage the breadth-first search; each int array holds two elements: position and step count.
20 Queue<int[]> queue = new ArrayDeque<>();
21 queue.offer(new int[]{start, 0}); // Initial position with 0 steps taken
22
23 // Main loop of breadth-first search
24 while (!queue.isEmpty()) {
25 int[] current = queue.poll();
26 int position = current[0];
27 int steps = current[1];
28
29 // Apply each operation with each number in the given array 'nums'
30 for (int num : nums) {
31 for (IntBinaryOperator operation : operations) {
32 int nextPosition = operation.applyAsInt(position, num);
33
34 // If goal is reached, return the number of steps taken plus one for the current operation
35 if (nextPosition == goal) {
36 return steps + 1;
37 }
38
39 // If the next position is within the bounds and not visited, add it to the queue
40 if (nextPosition >= 0 && nextPosition <= 1000 && !visited[nextPosition]) {
41 queue.offer(new int[]{nextPosition, steps + 1}); // Increment step count by 1
42 visited[nextPosition] = true;
43 }
44 }
45 }
46 }
47
48 // If the goal cannot be reached, return -1
49 return -1;
50 }
51}
52
1#include <vector>
2#include <functional>
3#include <queue>
4
5class Solution {
6public:
7 int minimumOperations(std::vector<int>& nums, int start, int goal) {
8 // Define a pair structure for storing value and the current step count.
9 using ValueStepPair = std::pair<int, int>;
10
11 // Define the operations that can be applied.
12 std::vector<std::function<int(int, int)>> operations{
13 [](int x, int y) { return x + y; },
14 [](int x, int y) { return x - y; },
15 [](int x, int y) { return x ^ y; },
16 };
17
18 // Create a visited array to track the numbers that have already been checked.
19 std::vector<bool> visited(1001, false);
20
21 // Initialize a queue to perform Breadth-First Search (BFS).
22 std::queue<ValueStepPair> queue;
23 queue.push({start, 0});
24
25 // Loop until the queue is empty.
26 while (!queue.empty()) {
27 // Get the front element of the queue.
28 auto [currentValue, currentStep] = queue.front();
29 queue.pop();
30
31 // Apply each operation with each number in the input array.
32 for (int num : nums) {
33 for (auto operation : operations) {
34 int nextValue = operation(currentValue, num);
35
36 // Check if the operation result matches the goal.
37 if (nextValue == goal) {
38 return currentStep + 1;
39 }
40
41 // If the result is within bounds and not visited, add it to the queue.
42 if (nextValue >= 0 && nextValue <= 1000 && !visited[nextValue]) {
43 queue.push({nextValue, currentStep + 1});
44 visited[nextValue] = true;
45 }
46 }
47 }
48 }
49
50 // If the goal can't be reached, return -1.
51 return -1;
52 }
53};
54
1function minimumOperations(nums: number[], start: number, goal: number): number {
2 const numLength = nums.length;
3
4 // Helper function to perform addition
5 const add = (x: number, y: number): number => x + y;
6
7 // Helper function to perform subtraction
8 const subtract = (x: number, y: number): number => x - y;
9
10 // Helper function to perform bitwise XOR
11 const xor = (x: number, y: number): number => x ^ y;
12
13 // Array of operations that can be performed
14 const operations = [add, subtract, xor];
15
16 // Use a boolean array to keep track of visited states
17 let visited = new Array(1001).fill(false);
18
19 // Initialize queue with the start value and step count of 0
20 let queue: Array<[number, number]> = [[start, 0]];
21 visited[start] = true;
22
23 // Process the queue until empty
24 while (queue.length) {
25 // Pop the first element from the queue
26 let [currentValue, currentStep] = queue.shift();
27
28 // Iterate over all numbers that can be used for operations
29 for (let i = 0; i < numLength; i++) {
30 // Apply each operation with the current number
31 for (let operation of operations) {
32 const nextValue = operation(currentValue, nums[i]);
33
34 // Check if we've reached the goal
35 if (nextValue === goal) {
36 return currentStep + 1;
37 }
38
39 // Add the result of the operation to the queue if it's valid and not visited
40 if (nextValue >= 0 && nextValue <= 1000 && !visited[nextValue]) {
41 visited[nextValue] = true;
42 queue.push([nextValue, currentStep + 1]);
43 }
44 }
45 }
46 }
47
48 // -1 indicates that the goal cannot be reached
49 return -1;
50}
51
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by the operations performed in the breadth-first search (BFS) algorithm implemented. On each iteration of the while
loop, the algorithm processes each number in nums
with each of the three operations (addition, subtraction, XOR).
Let N
be the length of the nums
list. At most 1001
different states can be visited since vis
array is of that size, and any number out of that range is not considered.
For every state, we perform 3 operations for each number in nums
. Hence, the total number of operations in the worst case would be at most 1001 * 3 * N
. Therefore, the time complexity is O(N)
.
Space Complexity
The space complexity includes the storage for the queue q
, the visited states vis
, and some auxiliary space for function calls and variables.
- The
vis
list contains a fixed space of1001
elements. - The queue
q
can, in the worst case, contain all possible states that have been visited. Since a state will not be revisited once marked in thevis
array, the maximum size of the queue would not exceed1001
.
Considering both the fixed array and queue, the space complexity is also O(1)
since these do not scale with the size of the input array nums
.
Note: The above complexities assume that integer addition, subtraction, and XOR operations are O(1)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!