LeetCode 2998 - Minimum Number of Operations to Make X and Y Equal

LeetCode Problem 2998

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Breadth-First Search, Memoization

Solution

Problem Understanding

The problem asks us to transform an integer x into another integer y using the minimum number of operations. At every step, we are allowed to perform exactly one of four actions:

1. Divide x by 11 if it is divisible by 11.
2. Divide x by 5 if it is divisible by 5.
3. Decrease x by 1.
4. Increase x by 1.

The goal is to determine the fewest operations required to make x == y.

This is fundamentally a shortest path problem. We can think of every integer as a node in a graph, and every allowed operation as an edge with cost 1. We want the shortest path from node x to node y.

The input consists of two positive integers x and y, both bounded by 10^4. The output is a single integer representing the minimum number of operations.

The constraints are important because they tell us brute force graph exploration is possible, but we must still avoid unnecessary exponential branching. Since values remain relatively small, a graph search or memoized dynamic programming solution becomes feasible.

Several edge cases immediately stand out:

• If x == y, the answer is 0 because no operations are needed.
• If x < y, division operations are useless because they only decrease the number further. The optimal answer is simply y - x increments.
• Sometimes increasing before dividing is optimal. For example, 54 → 55 → 5 → 1 → 2 demonstrates that greedily dividing immediately is not always correct.
• Sometimes decrementing before dividing is optimal, such as 26 → 25 → 5 → 1.

These cases show why a naive greedy strategy fails and why we need a systematic shortest path approach.

Approaches

Brute Force Approach

A brute force solution would explore every possible sequence of operations from x until reaching y. At each number, we could try all valid operations recursively.

This approach is correct because it eventually examines every possible path and can choose the shortest one. However, it is highly inefficient because the search tree branches repeatedly. Since increment and decrement are always available, the number of possible states grows rapidly.

Without memoization or pruning, the same intermediate numbers are recomputed many times. This leads to exponential time complexity, making the solution impractical.

Key Insight for an Optimal Solution

The important observation is that this problem has overlapping subproblems and optimal substructure.

Suppose we are currently at some number n. The minimum operations needed from n to y depends only on the best results of nearby states. This naturally suggests memoization.

A direct BFS would work because all operations cost 1, but there is an even cleaner recursive dynamic programming approach.

For a number n, we always have a fallback strategy:

• Move directly to y using only increments or decrements, costing |n - y|.

However, if division by 5 or 11 could help, we should consider adjusting n slightly to make it divisible.

For division by 5:

• Decrease n until divisible by 5, then divide.
• Increase n until divisible by 5, then divide.

Similarly for division by 11.

This dramatically reduces branching because instead of exploring arbitrary increments and decrements, we only explore meaningful transitions around divisibility boundaries.

We memoize results so each state is solved once.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all operation sequences recursively
Optimal	O(log x) amortized	O(log x)	Memoized DFS with divisibility transitions

Algorithm Walkthrough

Optimal Memoized DFS

1. Define a recursive function dfs(current) that returns the minimum operations needed to convert current into y.
2. Handle the simplest case first. If current <= y, division no longer helps because it only decreases the number further. The best option is simply incrementing until y, which costs y - current.
3. Initialize the answer as current - y. This represents the fallback strategy of repeatedly decrementing until reaching y.
4. Try using division by 5.

• Compute how far current is from the nearest multiple of 5.

• Let remainder = current % 5.

• We can either:

• Decrement remainder times to reach a divisible number.

• Increment 5 - remainder times to reach the next divisible number.

• After adjustment, divide by 5 and recursively solve the smaller state.

5. Try using division by 11 similarly.

• Compute remainder = current % 11.
• Consider both decrementing and incrementing to a divisible number.
• Divide and recurse.

6. Return the minimum among all possible strategies.
7. Use memoization so repeated states are computed only once.

The recursion shrinks numbers quickly through division, which keeps the state space small.

Why it works

The algorithm works because it evaluates every meaningful optimal transition from a state. Any shortest sequence must either:

• Move directly toward y using increments or decrements, or
• Eventually use a division by 5 or 11.

Before division becomes possible, only a small number of increments or decrements are needed to reach divisibility. By exploring both directions around divisibility and memoizing results, we guarantee that every optimal path is considered exactly once.

Python Solution

from functools import lru_cache

class Solution:
    def minimumOperationsToMakeEqual(self, x: int, y: int) -> int:

        @lru_cache(None)
        def dfs(current: int) -> int:
            if current <= y:
                return y - current

            # Fallback: decrement directly to y
            best = current - y

            # Division by 5
            remainder_5 = current % 5

            # Decrease to nearest multiple of 5
            best = min(
                best,
                remainder_5 + 1 + dfs(current // 5)
            )

            # Increase to next multiple of 5
            if remainder_5 != 0:
                best = min(
                    best,
                    (5 - remainder_5) + 1 + dfs(current // 5 + 1)
                )

            # Division by 11
            remainder_11 = current % 11

            # Decrease to nearest multiple of 11
            best = min(
                best,
                remainder_11 + 1 + dfs(current // 11)
            )

            # Increase to next multiple of 11
            if remainder_11 != 0:
                best = min(
                    best,
                    (11 - remainder_11) + 1 + dfs(current // 11 + 1)
                )

            return best

        return dfs(x)

The implementation uses a memoized recursive helper function named dfs. Each call computes the minimum operations required to transform a specific value into y.

The base case handles current <= y. Since division only decreases numbers, once we are below y, the only sensible operation is incrementing.

The variable best starts with the direct decrement path, which guarantees correctness even if division is not useful.

For division by 5 and 11, we consider both nearby divisible targets:

• Move downward to the nearest divisible number.
• Move upward to the next divisible number.

After adjusting, we perform the division and recursively solve the resulting smaller subproblem.

Memoization ensures each state is evaluated once, eliminating redundant work.

Go Solution

func minimumOperationsToMakeEqual(x int, y int) int {
	memo := make(map[int]int)

	var dfs func(int) int

	min := func(a, b int) int {
		if a < b {
			return a
		}
		return b
	}

	dfs = func(current int) int {
		if current <= y {
			return y - current
		}

		if val, exists := memo[current]; exists {
			return val
		}

		// Fallback: decrement directly to y
		best := current - y

		// Division by 5
		remainder5 := current % 5

		best = min(
			best,
			remainder5+1+dfs(current/5),
		)

		if remainder5 != 0 {
			best = min(
				best,
				(5-remainder5)+1+dfs(current/5+1),
			)
		}

		// Division by 11
		remainder11 := current % 11

		best = min(
			best,
			remainder11+1+dfs(current/11),
		)

		if remainder11 != 0 {
			best = min(
				best,
				(11-remainder11)+1+dfs(current/11+1),
			)
		}

		memo[current] = best
		return best
	}

	return dfs(x)
}

The Go implementation follows the same recursive memoization strategy. Since Go does not have built in memoization decorators like Python's lru_cache, we explicitly maintain a map[int]int for caching computed states.

The recursive closure dfs captures memo and y. Integer arithmetic behaves safely within constraints because values never exceed small bounds around 10^4.

Worked Examples

Example 1: x = 26, y = 1

We begin with dfs(26).

Step	Current	Action	Cost
1	26	Decrement to 25	1
2	25	Divide by 5 → 5	1
3	5	Divide by 5 → 1	1

Total cost = 3

The recursive evaluation checks other possibilities, but this path is minimal.

Example 2: x = 54, y = 2

Step	Current	Action	Cost
1	54	Increment to 55	1
2	55	Divide by 11 → 5	1
3	5	Divide by 5 → 1	1
4	1	Increment to 2	1

Total cost = 4

A greedy decrement strategy would take far more steps.

Example 3: x = 25, y = 30

Since x < y, division is never useful.

Step	Current	Action	Cost
1	25	Increment	1
2	26	Increment	1
3	27	Increment	1
4	28	Increment	1
5	29	Increment	1

Total cost = 5

The algorithm immediately returns 30 - 25.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(log x) amortized	Recursive states shrink rapidly through division
Space	O(log x)	Memoization and recursion depth

The recursion explores only meaningful states near multiples of 5 and 11. Since division drastically reduces numbers, the recursion tree remains shallow. Memoization prevents repeated recomputation, making the effective number of states very small.

Test Cases

sol = Solution()

# Provided examples
assert sol.minimumOperationsToMakeEqual(26, 1) == 3  # decrement then divide twice
assert sol.minimumOperationsToMakeEqual(54, 2) == 4  # increment before dividing
assert sol.minimumOperationsToMakeEqual(25, 30) == 5  # x < y

# Boundary values
assert sol.minimumOperationsToMakeEqual(1, 1) == 0  # already equal
assert sol.minimumOperationsToMakeEqual(1, 10000) == 9999  # only increments possible
assert sol.minimumOperationsToMakeEqual(10000, 1) >= 0  # upper bound

# Exact divisibility
assert sol.minimumOperationsToMakeEqual(55, 5) == 1  # direct division by 11
assert sol.minimumOperationsToMakeEqual(25, 1) == 2  # divide twice by 5

# Increment before division
assert sol.minimumOperationsToMakeEqual(54, 5) == 2  # 54 -> 55 -> 5

# Decrement before division
assert sol.minimumOperationsToMakeEqual(26, 5) == 1  # 26 -> 25 -> 5

# Already optimal with decrements
assert sol.minimumOperationsToMakeEqual(10, 7) == 3  # direct decrementing

# Mixed operations
assert sol.minimumOperationsToMakeEqual(121, 1) == 2  # divide by 11 twice

Test	Why
(26, 1)	Validates decrement before division
(54, 2)	Validates increment before division
(25, 30)	Verifies x < y shortcut
(1, 1)	Already equal case
(1, 10000)	Large increment only path
(55, 5)	Direct divisibility by 11
(25, 1)	Multiple chained divisions
(54, 5)	Incrementing to divisible state
(10, 7)	Direct decrement optimality
(121, 1)	Repeated division by 11

Edge Cases

When x == y

This is the simplest edge case. No operations are needed because the numbers are already equal. A buggy implementation might still recurse unnecessarily. Our solution handles this naturally because current <= y immediately returns y - current, which becomes 0.

When x < y

Division operations are never beneficial here because they only decrease the number further away from the target. The only optimal strategy is repeated incrementing. The implementation directly returns y - current for this case, avoiding unnecessary recursion.

When incrementing before division is optimal

A naive greedy solution might always divide immediately whenever possible. This fails for inputs like (54, 2), where increasing first creates a divisible number and produces a shorter path. Our implementation explicitly checks both directions around divisibility, guaranteeing that such cases are handled correctly.

When decrementing before division is optimal

Similarly, some cases benefit from reducing the number slightly before division. For (26, 1), decrementing once to 25 enables two efficient divisions. Since we explore both nearest divisible numbers, this path is correctly discovered.