Minimum Number of Operations to Make X and Y Equal

medium bfs dp memoization

Problem

You are given two positive integers x and y. In one operation you may do any of the following to x: divide it by 11 (only when x is a multiple of 11), divide it by 5 (only when x is a multiple of 5), subtract 1, or add 1. Return the smallest number of operations needed to turn x into y.

Inputx = 26, y = 1

Output3

26 → 25 (subtract 1) → 5 (divide by 5) → 1 (divide by 5). Three operations, which is the fewest possible.

from collections import deque

def minimum_operations(x, y):
    if x <= y:
        return y - x
    seen = {x}
    q = deque([x])
    steps = 0
    while q:
        for _ in range(len(q)):
            v = q.popleft()
            if v == y:
                return steps
            nxt = [v - 1, v + 1]
            if v % 11 == 0:
                nxt.append(v // 11)
            if v % 5 == 0:
                nxt.append(v // 5)
            for w in nxt:
                if w >= 0 and w not in seen:
                    seen.add(w)
                    q.append(w)
        steps += 1
    return steps

function minimumOperations(x, y) {
  if (x <= y) return y - x;
  const seen = new Set([x]);
  let q = [x];
  let steps = 0;
  while (q.length) {
    const next = [];
    for (const v of q) {
      if (v === y) return steps;
      const cand = [v - 1, v + 1];
      if (v % 11 === 0) cand.push(v / 11);
      if (v % 5 === 0) cand.push(v / 5);
      for (const w of cand) {
        if (w >= 0 && !seen.has(w)) {
          seen.add(w);
          next.push(w);
        }
      }
    }
    q = next;
    steps += 1;
  }
  return steps;
}

class Solution {
    public int minimumOperations(int x, int y) {
        if (x <= y) return y - x;
        Set<Integer> seen = new HashSet<>();
        seen.add(x);
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        int steps = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int v = q.poll();
                if (v == y) return steps;
                int[] cand = buildMoves(v);
                for (int w : cand) {
                    if (w >= 0 && seen.add(w)) q.add(w);
                }
            }
            steps += 1;
        }
        return steps;
    }
}

int minimumOperations(int x, int y) {
    if (x <= y) return y - x;
    unordered_set<int> seen{ x };
    queue<int> q;
    q.push(x);
    int steps = 0;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            int v = q.front(); q.pop();
            if (v == y) return steps;
            vector<int> cand = { v - 1, v + 1 };
            if (v % 11 == 0) cand.push_back(v / 11);
            if (v % 5 == 0) cand.push_back(v / 5);
            for (int w : cand) {
                if (w >= 0 && !seen.count(w)) {
                    seen.insert(w);
                    q.push(w);
                }
            }
        }
        steps += 1;
    }
    return steps;
}

Explanation

Every operation turns one number into another number, and each move costs exactly one step. That makes this a shortest-path question on a graph where the nodes are integer values and the edges are the four allowed moves. The natural tool for "fewest moves" on an unweighted graph is a breadth-first search (BFS).

Starting from x, we explore all values reachable in one move, then all values reachable in two moves, and so on, layer by layer. The first time the search touches y, the number of layers we have peeled off is the minimum number of operations. A seen set (this is the memoization) makes sure we never revisit a value, so the search stays fast and never loops.

From a value v the moves are: v − 1, v + 1, v / 11 when v is divisible by 11, and v / 5 when v is divisible by 5. We only enqueue non-negative values we have not seen before.

One quick shortcut: if x ≤ y the only useful move is +1 (dividing makes x smaller, which is the wrong direction), so the answer is simply y − x.

Example: x = 26, y = 1. Layer 1 from 26 gives {25, 27} (26 is not divisible by 5 or 11). Layer 2 expands 25 into {24, 26→seen, 5} and 27 into {26→seen, 28}, so we discover 5. Layer 3 expands 5 into {4, 6, 1} — we reach 1, so the answer is 3.

Because each value is processed once and produces at most four neighbours, BFS reaches y in the fewest possible moves.

Time: O(x) Space: O(x)