2059. Minimum Operations to Convert Number

MediumBreadth-First SearchArray
Leetcode Link

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] to x (x + nums[i])
  • Subtracting any number nums[i] from x (x - nums[i])
  • Performing a bitwise-XOR between x and any number nums[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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

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:

  1. A boolean visited array vis of size 1001 is used to keep track of numbers in the range 0 to 1000 that have already been explored. Initially, all values are set to False since no numbers have been explored.

  2. A queue q is initiated with a tuple containing the start number and step counter set to 0. The Python deque (double-ended queue) is chosen for efficiency since we need to add and remove elements from both ends.

  3. 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 in nums.
    • For each number num, we apply the three operations using the previously defined lambdas. The result of each operation is stored in nx.

  4. For each result nx, we check if nx equals the goal. If it does, we have found the shortest path to goal and return the current step count plus one, because we have made another operation to reach goal.

  5. If nx is within the bounds (0 <= nx <= 1000) and has not been visited before, we add (nx, step + 1) to the queue and mark nx as visited.

  6. If the queue is emptied and goal has not been found, this implies that it is not possible to convert start into goal 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's illustrate the solution with a small example:

Assume nums = [2, 3], start = 0, and goal = 10.

  1. We begin by initiating the BFS process with the starting point. Our queue q = [(0, 0)], where 0 is the initial value of x and 0 is the step counter. The visited array vis is set to False for all values.

  2. The BFS starts by dequeuing the first element (0, 0) from q. We perform all three operations on x with each number in nums.

  3. After applying the operations (add, subtract, XOR) with num = 2, we get three possibilities: x + 2 = 2, x - 2 = -2, and x ^ 2 = 2. The second result is out of bounds, so only 2 will be queued: q = [(2, 1)].

    Repeating with num = 3, we get x + 3 = 3, x - 3 = -3, and x ^ 3 = 3. Again, "-3" is out of bounds, and since 3 is not yet visited, we add it to the queue. Now q = [(2, 1), (3, 1)].

  4. Next, we dequeue (2, 1) and repeat the operations with all nums:

    With num = 2, we get 2 + 2 = 4, 2 - 2 = 0 (already visited), and 2 ^ 2 = 0 (already visited).

    With num = 3, we get 2 + 3 = 5, 2 - 3 = -1 (out of bounds), and 2 ^ 3 = 1. The new numbers 4 and 1 are added to the queue, while 0 is ignored. Now, q = [(3, 1), (4, 2), (1, 2)].

  5. This process continues as we dequeue from q, apply operations, and enqueue non-visited results until we either achieve the goal of 10 or empty the queue.

    After more iterations, we might eventually reach a state where q includes (10, N), where N is the number of operations taken. At this point, we return N + 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
Not Sure What to Study? Take the 2-min Quiz：

What data structure does Breadth-first search typically uses to store intermediate states?

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 of 1001 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 the vis array, the maximum size of the queue would not exceed 1001.

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.

Fast Track Your Learning with Our Quick Skills Quiz:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

Recommended Readings

BFS Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

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

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫