Minimum Number of Operations to Make X and Y Equal — Editorial

Opening the reading…

Intuitionwhy shortest paths fit the operations exactly

Treat every nonnegative integer as a state. From a state cur, one operation can move to cur - 1, cur + 1, cur / 5 when divisible by 5, or cur / 11 when divisible by 11. Every move costs exactly one operation, so the answer is the length of the shortest path from x to y in this unweighted graph.

When x is already below y, increasing directly is optimal: every useful path must gain at least y - x, and adding a division would only move away from the target before requiring more increases. When x is above y, repeated decrements give a fallback of x - y operations. A better path may first increase to a nearby multiple of 5 or 11, divide, and then finish with fewer moves.

BFS explores states in order of the number of operations used to reach them. The first time it reaches y, no later path can be shorter. We only need to explore up to x + (x - y): the direct-decrement path already costs x - y, so any path that climbs above this limit has already spent more operations increasing than that complete candidate costs.

Division edges can make a path that temporarily increases x shorter overall.

Approach

If x equals y, return 0 immediately, because the empty sequence already makes the values equal and no operation can improve on it.

If x is less than y, return y - x, because direct increments achieve the required increase and any division would create extra work to recover the lost value.

For x greater than y, set the upper limit to x + (x - y), because repeated decrements provide a path of length x - y and no optimal path needs to visit a state above that limit.

Create a distance array initialized to -1 and a queue, mark x with distance 0, and enqueue it. The distance array both records the number of operations and prevents cycles such as incrementing and then decrementing forever.

Remove states from the front of the queue and return the stored distance as soon as the state equals y, because BFS removes states in nondecreasing distance order.

Try cur - 1 and cur + 1 when they stay inside the allowed range, because both are always legal one-operation moves and may be part of the shortest route.

If cur is divisible by 5 or 11, enqueue the corresponding quotient when it is unvisited. These conditional edges are the useful shortcuts; applying division to a non-multiple would create an operation the problem does not allow.

Assign distance d + 1 when a state is first enqueued, not when it is removed, because the first discovered route is already shortest and duplicate queue entries would waste time and obscure the distance.

Complexitythe bounded state graph has constant degree

MEASURE	BOUND	WHY
Time	O(U)	Each integer from 0 through U enters the queue at most once. Each state checks at most four constant-time transitions, so the total work is proportional to the number of explored states rather than to the number of possible paths.
Space	O(U) extra	The distance array and queue together store at most one record per bounded state; the graph is generated on demand, so no edge list is stored. The returned value is a single integer and is output storage, not working memory. In the worst shape of the input range, x = 10^4 and y = 1, U is 19999.

Here U means the largest explored value, U = x + (x - y) = 2x - y, for the only branch where x > y. Since 1 <= x,y <= 10^4, U is less than 2 x 10^4.

Annotated solutionC++ · bounded BFS over integer states

CPPBFS visits each bounded integer once and generates all legal one-operation moves.

#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    int minimumOperationsToMakeEqual(int x, int y) {
        if (x == y) {
            return 0;
        }
        if (x < y) {
            return y - x;
        }

        int limit = x + (x - y);
        vector<int> distance(limit + 1, -1);
        queue<int> states;

        distance[x] = 0;
        states.push(x);

        while (!states.empty()) {
            int cur = states.front();
            states.pop();
            int steps = distance[cur];

            if (cur == y) {
                return steps;
            }

            if (cur > 0 && distance[cur - 1] == -1) {
                distance[cur - 1] = steps + 1;
                states.push(cur - 1);
            }

            if (cur < limit && distance[cur + 1] == -1) {
                distance[cur + 1] = steps + 1;
                states.push(cur + 1);
            }

            if (cur % 5 == 0 && distance[cur / 5] == -1) {
                distance[cur / 5] = steps + 1;
                states.push(cur / 5);
            }

            if (cur % 11 == 0 && distance[cur / 11] == -1) {
                distance[cur / 11] = steps + 1;
                states.push(cur / 11);
            }
        }

        return -1;
    }
};

The limit is derived from the fallback path, not chosen as an arbitrary large constant. For x > y, the direct route takes d = x - y operations. Reaching a value greater than x + d requires more than d increments from the starting value alone, so that route is already longer than a known valid answer. The optimal path therefore remains inside the bounded array.

The divisibility tests must happen before the quotient is enqueued. Division by 5 and division by 11 are edges only from exact multiples; the problem does not permit rounding. Marking a state when enqueuing it is equally important, because all edges have unit cost and the first route to a state is the shortest route to it.