#2998

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Minimum Number of Operations to Make X and Y Equal

Determine the minimum operations to make two integers equal using increment, decrement, and division efficiently with DP.

dynamic programming breadth first search memoization

Problem Statement

You are given two positive integers x and y. In each operation, you can either increment x by 1, decrement x by 1, or divide x by 5 or 11 if divisible. Determine the fewest number of operations required to make x equal to y.

Return an integer representing the minimum number of operations. Consider sequences where x may need multiple divisions interleaved with increments or decrements. The solution must efficiently handle all cases within 1 <= x, y <= 104 using state transition dynamic programming.

Examples

Example 1

Input: x = 26, y = 1

Output: 3

We can make 26 equal to 1 by applying the following operations:

Decrement x by 1
Divide x by 5
Divide x by 5 It can be shown that 3 is the minimum number of operations required to make 26 equal to 1.

Example 2

Input: x = 54, y = 2

Output: 4

We can make 54 equal to 2 by applying the following operations:

Increment x by 1
Divide x by 11
Divide x by 5
Increment x by 1 It can be shown that 4 is the minimum number of operations required to make 54 equal to 2.

Example 3

Input: x = 25, y = 30

Output: 5

We can make 25 equal to 30 by applying the following operations:

Increment x by 1
Increment x by 1
Increment x by 1
Increment x by 1
Increment x by 1 It can be shown that 5 is the minimum number of operations required to make 25 equal to 30.

Constraints

1 <= x, y <= 104

Solution Approach

Direct Increment Check

If y is greater than or equal to x, the minimum operations equal y - x, because the only way to increase x is by incrementing. This provides an immediate solution in such cases without further computation.

Dynamic Programming with Memoization

Define a function dp(n) representing the minimum operations to reduce n to y. Apply allowed operations recursively with memoization to avoid repeated calculations. Use state transitions to choose the operation that leads to the minimum path.

Breadth-First Search Approach

Treat each integer value as a node in a graph. Explore all possible operations from the current state using BFS to find the shortest sequence reaching y. This guarantees finding the minimum number of steps while handling interleaved increments, decrements, and divisions.

Complexity Analysis

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

Time and space complexity depend on the method chosen. BFS explores reachable states with O(max(x, y)) in practice, while DP with memoization reduces repeated computations, making the approach efficient within constraints 1 <= x, y <= 104.

What Interviewers Usually Probe

Are you considering cases where x needs multiple divisions before reaching y?
How does your DP handle memoization to avoid recomputing states?
What is the immediate solution when y is greater than or equal to x?

Common Pitfalls or Variants

Common pitfalls

Forgetting that increments are the only way to increase x and directly returning y - x when y >= x.
Not memoizing intermediate states, which leads to redundant computations and timeout.
Applying divisions without checking divisibility by 5 or 11, resulting in invalid state transitions.

Follow-up variants

Compute minimum operations if only increment and decrement are allowed without division.
Find the minimum operations to make x equal y using a different set of divisors, like 2 and 3.
Determine operations if division results must be rounded down instead of integer division.

FAQ

What is the fastest way to handle cases where y >= x in this problem?

Simply increment x by 1 repeatedly until it equals y. The number of steps is y - x, as no divisions can increase x.

How does state transition dynamic programming apply here?

Each number represents a state. Operations like increment, decrement, or division transition to new states. DP computes minimum steps for each state efficiently.

Can BFS find the minimum operations for all inputs?

Yes, BFS explores all reachable numbers from x, guaranteeing the shortest path to y while correctly handling interleaved operations.

Do I need to check divisibility before applying division operations?

Yes, only divide x by 5 or 11 if it is divisible to ensure valid state transitions and correct minimum step count.

What common mistakes should I avoid when implementing the solution?

Avoid forgetting y >= x shortcut, skipping memoization in DP, and applying divisions without checking divisibility, which can cause errors or inefficiency.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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)

Continue Practicing

#2328 number of increasing paths in a grid #3040 maximum number of operations with the same score ii #2920 maximum points after collecting coins from all nodes