MediumNo. 2059
Minimum Operations to Convert Number — LeetCode 2059 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Breadth-First Search, Array
- Reading time
- 4 min
- Source
- leetcode.com
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 -1Complexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
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
| No. | Problem | Difficulty |
|---|---|---|
| 0864 | Shortest Path to Get All Keys | Hard |
| 0909 | Snakes and Ladders | Medium |
| 0994 | Rotting Oranges | Medium |
| 1091 | Shortest Path in Binary Matrix | Medium |
| 1210 | Minimum Moves to Reach Target with Rotations | Hard |
| 1293 | Shortest Path in a Grid with Obstacles Elimination | Hard |
Frequently asked questions
- How hard is LeetCode 2059. Minimum Operations to Convert Number?
LeetCode 2059. Minimum Operations to Convert Number is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2059. Minimum Operations to Convert Number?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 2059. Minimum Operations to Convert Number?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 2059. Minimum Operations to Convert Number cover?
LeetCode 2059. Minimum Operations to Convert Number is tagged Breadth-First Search and Array on LeetCode.