Minimum Number of Operations to Make X and Y Equal — LeetCode 2998 Python Solution

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

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