Digit Operations to Make Two Integers Equal

• Pre-compute prime numbers up to 9999 using a sieve.
• Check if the initial n or target m are prime. If either is, a solution is impossible, so return -1.
• Initialize a global variable min_cost to infinity.
• Create a recursive function, let's call it dfs(u, current_cost, path):
  • u: the current number.
  • current_cost: the sum of numbers in the path so far.
  • path: a set of numbers visited in the current path to avoid cycles.
• The base case for the recursion is when u == m. If so, update min_cost = min(min_cost, current_cost).
• Add a pruning step: if current_cost >= min_cost, stop exploring this path.
• In the recursive step, generate all valid neighbors v of u.
• A neighbor v is valid if it's reachable by one digit operation, is not prime, and is not in the current path.
• For each valid neighbor v, make a recursive call: dfs(v, current_cost + v, new_path_with_v).
• Start the search by calling dfs(n, n, {n}).
• After the search is complete, if min_cost is still infinity, it means m is unreachable. Otherwise, min_cost holds the answer.

The core of this method is a recursive function that explores paths starting from n. The function takes the current number, the accumulated cost, and the set of visited nodes in the current path as arguments.

When the function reaches the target m, it compares the path's cost with the global minimum and updates it if the new path is cheaper. To optimize slightly, the recursion is pruned if the current path's cost already exceeds the best-known minimum cost.

However, because the number of possible paths can be enormous, this method is not practical for the given constraints. It explores paths one by one without prioritizing potentially cheaper paths, leading to a very large search space. For example, it might explore a very long and expensive path completely before trying a short and cheap one.

Here is a conceptual outline of the DFS function:

1long minCost = Long.MAX_VALUE;2boolean[] isPrime;3 4void solve(int n, int m) {5    // Sieve pre-computation6    sieve(9999);7    if (isPrime[n] || isPrime[m]) {8        // return -1;9        return;10    }11    Set<Integer> path = new HashSet<>();12    path.add(n);13    dfs(n, m, n, path);14    // return minCost == Long.MAX_VALUE ? -1 : minCost;15}16 17void dfs(int u, int m, long currentCost, Set<Integer> path) {18    if (currentCost >= minCost) {19        return; // Pruning20    }21    if (u == m) {22        minCost = Math.min(minCost, currentCost);23        return;24    }25 26    for (int v : getNeighbors(u)) { // getNeighbors generates valid next numbers27        if (!path.contains(v)) {28            path.add(v);29            dfs(v, m, currentCost + v, path);30            path.remove(v); // Backtrack31        }32    }33}

• Special Case: If n == m, no operations are needed, so the cost is 0. Return 0.
• Preprocessing: Generate all prime numbers up to 9999 using the Sieve of Eratosthenes. This allows for O(1) primality checks.
• Initial Checks: If n or m is prime, a valid transformation is impossible. Return -1.
• Graph Model: Treat the integers as nodes in a graph. A directed edge exists from u to v if v can be obtained from u via a single valid digit operation.
• Dijkstra's Algorithm Setup:
  • The cost of a path v_0, v_1, ..., v_k is v_0 + v_1 + ... + v_k.
  • The cost to reach a neighbor v from u is dist[u] + v, where dist[u] is the minimum cost to reach u.
  • Initialize a dist array with infinity for all nodes, and set dist[n] = n.
  • Use a priority queue to store pairs of (cost, node), ordered by cost.
• Execution:
  • Add (n, n) to the priority queue.
  • While the priority queue is not empty, extract the node u with the smallest cost.
  • If u is the target m, dist[m] contains the minimum total cost. Return dist[m].
  • For each valid neighbor v of u (not prime, same number of digits):
    • If dist[u] + v < dist[v], update dist[v] = dist[u] + v and add (dist[v], v) to the priority queue.
• No Path: If the loop finishes before m is reached, m is unreachable. Return -1.

The key insight is to recognize this as a shortest path problem where the edge weights are not constant but depend on the destination node. The total cost of a path is the sum of the values of all nodes in it, including the start and end nodes. A Dijkstra-like algorithm is perfect for this.

Let dist[i] be the minimum cost to transform n into i. The cost is the sum of all numbers on the path. We initialize dist[n] = n and all other dist values to infinity. We use a priority queue to always explore the node with the current minimum accumulated cost.

When we are at a node u and consider moving to a neighbor v, the cost of the new path to v is dist[u] + v. If this is less than the currently known dist[v], we update dist[v] and add v to the priority queue. This process guarantees that when we first extract m from the priority queue, we have found the minimum cost path to it.

Initial checks for primality of n and m are crucial, as is handling the n == m case separately.

1import java.util.*;2 3class Solution {4    private boolean[] isPrime;5    private int numDigits;6 7    private void sieve(int max) {8        isPrime = new boolean[max + 1];9        Arrays.fill(isPrime, true);10        isPrime[0] = isPrime[1] = false;11        for (int p = 2; p * p <= max; p++) {12            if (isPrime[p]) {13                for (int i = p * p; i <= max; i += p) {14                    isPrime[i] = false;15                }16            }17        }18    }19 20    private List<Integer> getNeighbors(int u) {21        List<Integer> neighbors = new ArrayList<>();22        char[] digits = String.valueOf(u).toCharArray();23 24        for (int i = 0; i < digits.length; i++) {25            char originalDigit = digits[i];26            27            // Increase digit28            if (originalDigit < '9') {29                digits[i]++;30                int v = Integer.parseInt(new String(digits));31                if (!isPrime[v]) {32                    neighbors.add(v);33                }34            }35            36            digits[i] = originalDigit; // Backtrack37 38            // Decrease digit39            if (originalDigit > '0') {40                if (i == 0 && numDigits > 1 && originalDigit == '1') {41                    // This would change the number of digits (e.g., 10 -> 0), so skip.42                } else {43                    digits[i]--;44                    int v = Integer.parseInt(new String(digits));45                    if (!isPrime[v]) {46                        neighbors.add(v);47                    }48                }49            }50            digits[i] = originalDigit; // Backtrack51        }52        return neighbors;53    }54 55    public int minimumCost(int n, int m) {56        if (n == m) {57            return 0;58        }59        60        sieve(9999);61        62        if (isPrime[n] || isPrime[m]) {63            return -1;64        }65 66        numDigits = String.valueOf(n).length();67 68        long[] dist = new long[10000];69        Arrays.fill(dist, Long.MAX_VALUE);70        dist[n] = n;71 72        // Priority Queue stores {cost, number}73        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));74        pq.offer(new long[]{n, n});75 76        while (!pq.isEmpty()) {77            long[] current = pq.poll();78            long currentCost = current[0];79            int u = (int) current[1];80 81            if (currentCost > dist[u]) {82                continue;83            }84 85            if (u == m) {86                return (int) dist[m];87            }88 89            for (int v : getNeighbors(u)) {90                if (dist[u] != Long.MAX_VALUE && dist[u] + v < dist[v]) {91                    dist[v] = dist[u] + v;92                    pq.offer(new long[]{dist[v], v});93                }94            }95        }96 97        return -1;98    }99}