#2059

Medium

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Minimum Operations to Convert Number

Determine the minimum operations needed to convert a number using array elements with addition, subtraction, or XOR operations efficiently.

array breadth first search

Problem Statement

You are given an integer array nums of distinct numbers, a start value, and a goal value. Starting with x equal to start, you can repeatedly perform operations using elements from nums to convert x to goal. The allowed operations are addition, subtraction, or XOR with any nums[i], applied in any order, multiple times.

Operations are valid even if x moves outside the range 0 to 1000, but once x is out of this range, no further operations can be applied. Determine the fewest number of operations required to reach the goal from start, or return -1 if conversion is impossible.

Examples

Example 1

Input: nums = [2,4,12], start = 2, goal = 12

Output: 2

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

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

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.

Solution Approach

Breadth-First Search Traversal

Use BFS starting from the initial number. At each step, generate all possible next numbers by adding, subtracting, or XORing with each nums[i]. Keep a queue to process numbers in order of operation count, ensuring the first time you reach goal is minimal.

Visited Tracking and Pruning

Maintain a visited set for numbers within 0 to 1000 to prevent revisiting and infinite loops. Prune numbers outside this range after applying an operation since they cannot be extended further. This avoids unnecessary computation and ensures BFS efficiency.

Handling Out-of-Range Transitions

Allow a single operation to move x outside the 0-1000 range if it reaches goal. Any further operations beyond this range are invalid. Carefully check the goal at each step before pruning to correctly capture transitions that reach goal from out-of-range numbers.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the BFS traversal over the state space from start to goal, potentially O(n*range) where range is limited to numbers within 0 to 1000 plus immediate out-of-range transitions. Space complexity is O(range) for the visited set and queue.

What Interviewers Usually Probe

Does your solution correctly handle numbers that exceed 1000 or go below 0?
Are you efficiently avoiding revisiting states in the BFS queue?
Can you explain why BFS guarantees the minimum number of operations for this problem?

Common Pitfalls or Variants

Common pitfalls

Ignoring that numbers outside 0-1000 can only be used once for the final operation.
Failing to track visited numbers, leading to cycles or redundant computation.
Applying operations without checking whether the goal can be reached immediately when leaving the valid range.

Follow-up variants

Minimize operations using only addition and subtraction instead of including XOR.
Allow repeated elements from nums to be applied multiple times in sequence without BFS tracking.
Limit the operations so x must always remain within 0 to 1000, disallowing out-of-range moves.

FAQ

What operations can I perform to convert start to goal in Minimum Operations to Convert Number?

You can use addition, subtraction, or XOR with any element in nums repeatedly until reaching goal.

Can numbers go out of the 0-1000 range during operations?

Yes, a number can go out of range, but no further operations can be performed afterward except to check if goal is reached.

What is the main algorithmic pattern to solve this problem?

The problem follows the Array plus Breadth-First Search pattern, exploring states layer by layer to find minimal operations.

How do I track visited numbers efficiently?

Use a set or boolean array to mark numbers from 0 to 1000 once they are processed in BFS to avoid revisiting.

What should I return if there is no way to reach the goal?

Return -1 if BFS completes without reaching the goal.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class 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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class 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

Solution 3

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class 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

Continue Practicing

#2039 the time when the network becomes idle #2101 detonate the maximum bombs #1993 operations on tree