{x}
blog image

Minimum Operations to Convert Number

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.

Minimum Operations to Convert Number

This problem asks for the minimum number of operations to convert a starting number start to a target number goal using a given array of numbers nums. The allowed operations are addition, subtraction, and bitwise XOR with any element from nums.

Approach: Breadth-First Search (BFS)

The most efficient approach is to use Breadth-First Search (BFS). BFS systematically explores the search space level by level, guaranteeing that the shortest path (minimum number of operations) is found first.

Algorithm:

  1. Initialization:

    • Create a queue q initialized with the starting number start and its distance (0 operations).
    • Create a vis (visited) array or set to keep track of visited numbers to avoid cycles and redundant exploration.

  2. BFS Iteration:

    • While the queue is not empty:
      • Dequeue the current number x and its distance step from the queue.
      • For each number num in nums:
        • Apply each of the three operations (+, -, ^) with num to x, resulting in three new numbers (nx).
        • If any nx equals the goal, return step + 1 (the minimum number of operations).
        • If 0 <= nx <= 1000 and nx hasn't been visited:
          • Mark nx as visited.
          • Enqueue nx with its distance step + 1.

  3. No Solution:

    • If the queue becomes empty without finding the goal, it means no solution exists, so return -1.

Time Complexity Analysis

The time complexity is dominated by the BFS traversal. In the worst-case scenario, we might explore all numbers in the range [0, 1000]. For each number, we perform three operations with each number in nums. Therefore, the worst-case time complexity is O(1000 * nums.length). However, in practice, it will likely be much less due to the pruning of the search space using the visited array.

Space Complexity Analysis

The space complexity is primarily determined by the queue and the visited array/set. In the worst case, the queue can contain up to 1000 elements, and the visited array/set stores up to 1001 elements (0 to 1000). Therefore, the space complexity is O(1000), which is O(1) in terms of input size.

Code Implementation (Python)

from collections import deque
 
class Solution:
    def minimumOperations(self, nums: List[int], start: int, goal: int) -> int:
        q = deque([(start, 0)])  # (number, steps)
        visited = {start}
        while q:
            curr, steps = q.popleft()
            if curr == goal:
                return steps
            for num in nums:
                for next_num in [curr + num, curr - num, curr ^ num]:
                    if 0 <= next_num <= 1000 and next_num not in visited:
                        visited.add(next_num)
                        q.append((next_num, steps + 1))
        return -1

The code in other languages (Java, C++, Go, TypeScript) follows a similar structure, using their respective queue and set/map data structures to implement the BFS algorithm. The core logic remains the same.