Minimum Operations to Convert Number — LeetCode 2059 Python Solution

The problem

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.

Example

Input

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

Output

2

Explanation

We can go from 2 → 14 → 12 with the following 2 operations.

Python solution

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

Complexity

Pattern: Breadth-First Search

Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 2059. Minimum Operations to Convert Number is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Breadth-First Search.

The breadth-first search guide has the Python template for the pattern and the 233 LeetCode problems that use it.

Related problems