MediumNo. 2998
Minimum Number of Operations to Make X and Y Equal — LeetCode 2998 Python Solution
- Pattern
- Breadth-First Search
- Topics
- Breadth-First Search, Memoization, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given two positive integers x and y. In one operation, you can do one of the four following operations: Divide x by 11 if x is a multiple of 11.
Example
- Input
- x = 26, y = 1
- Output
- 3
- Explanation
- We can make 26 equal to 1 by applying the following operations:
Python solution
class Solution:
def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:
@cache
def dfs(x: int) -> int:
if y >= x:
return y - x
ans = x - y
ans = min(ans, x % 5 + 1 + dfs(x // 5))
ans = min(ans, 5 - x % 5 + 1 + dfs(x // 5 + 1))
ans = min(ans, x % 11 + 1 + dfs(x // 11))
ans = min(ans, 11 - x % 11 + 1 + dfs(x // 11 + 1))
return ans
return dfs(x)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Breadth-First Search
Expand outward level by level, so the first time you arrive is the shortest way. LeetCode 2998. Minimum Number of Operations to Make X and Y Equal is filed here because LeetCode tags it Breadth-First Search, which is the vocabulary this hub collects.
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 |
|---|---|---|
| 0329 | Longest Increasing Path in a Matrix | Hard |
| 0488 | Zuma Game | Hard |
| 0773 | Sliding Puzzle | Hard |
| 2328 | Number of Increasing Paths in a Grid | Hard |
| 0070 | Climbing Stairs | Easy |
| 0241 | Different Ways to Add Parentheses | Medium |
Frequently asked questions
- How hard is LeetCode 2998. Minimum Number of Operations to Make X and Y Equal?
LeetCode 2998. Minimum Number of Operations to Make X and Y Equal is rated Medium on LeetCode.
- What topics does LeetCode 2998. Minimum Number of Operations to Make X and Y Equal cover?
LeetCode 2998. Minimum Number of Operations to Make X and Y Equal is tagged Breadth-First Search, Memoization and Dynamic Programming on LeetCode.