# Digit Operations to Make Two Integers Equal
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/digit-operations-to-make-two-integers-equal)
Canonical: https://scaleengineer.com/dsa/problems/digit-operations-to-make-two-integers-equal
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Algorithms:** [Shortest Path](https://scaleengineer.com/algorithms/shortest-path)
**Data structures:** Heap (Priority Queue), Graph
---
## Problem
You are given two integers `n` and `m` that consist of the **same** number of digits.

You can perform the following operations **any** number of times:

* Choose **any** digit from `n` that is not 9 and **increase** it by 1.
* Choose **any** digit from `n` that is not 0 and **decrease** it by 1.

The integer `n` must not be a prime number at any point, including its original value and after each operation.

The cost of a transformation is the sum of **all** values that `n` takes throughout the operations performed.

Return the **minimum** cost to transform `n` into `m`. If it is impossible, return -1.

**Example 1:**

**Input:** n = 10, m = 12

**Output:** 85

**Explanation:**

We perform the following operations:

* Increase the first digit, now `n = **2**0`.
* Increase the second digit, now `n = 2**1**`.
* Increase the second digit, now `n = 2**2**`.
* Decrease the first digit, now `n = **1**2`.

**Example 2:**

**Input:** n = 4, m = 8

**Output:** \-1

**Explanation:**

It is impossible to make `n` equal to `m`.

**Example 3:**

**Input:** n = 6, m = 2

**Output:** \-1

**Explanation:** 

Since 2 is already a prime, we can't make `n` equal to `m`.

**Constraints:**

* `1 <= n, m < 104`
* `n` and `m` consist of the same number of digits.

# Approaches
## Brute-Force Depth First Search
This approach uses a classic brute-force Depth First Search (DFS) to explore all possible valid transformation sequences from `n` to `m`. It recursively explores each path, calculates its total cost, and keeps track of the minimum cost found. To prevent infinite loops, it avoids visiting the same number twice within a single path.
**Time:** O(B^D), where B is the branching factor (up to 8 neighbors per number) and D is the maximum path depth. This is exponential and far too slow for the given constraints. · **Space:** O(V), where V is the number of non-prime integers up to 9999. The recursion depth and the `path` set can, in the worst case, include all possible nodes.
**Pros:** Conceptually simple and relatively easy to understand for those familiar with recursion.
**Cons:** Extremely inefficient due to exploring a potentially exponential number of paths.; Almost certain to fail with a 'Time Limit Exceeded' error for the given constraints.; State management is complex to avoid cycles while allowing nodes to be revisited via different, potentially cheaper, paths.
### Explanation
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:
```java
long minCost = Long.MAX_VALUE;
boolean[] isPrime;

void solve(int n, int m) {
    // Sieve pre-computation
    sieve(9999);
    if (isPrime[n] || isPrime[m]) {
        // return -1;
        return;
    }
    Set<Integer> path = new HashSet<>();
    path.add(n);
    dfs(n, m, n, path);
    // return minCost == Long.MAX_VALUE ? -1 : minCost;
}

void dfs(int u, int m, long currentCost, Set<Integer> path) {
    if (currentCost >= minCost) {
        return; // Pruning
    }
    if (u == m) {
        minCost = Math.min(minCost, currentCost);
        return;
    }

    for (int v : getNeighbors(u)) { // getNeighbors generates valid next numbers
        if (!path.contains(v)) {
            path.add(v);
            dfs(v, m, currentCost + v, path);
            path.remove(v); // Backtrack
        }
    }
}
```
### Algorithm
- 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.

## Shortest Path on a Graph using Dijkstra's Algorithm
This problem can be efficiently solved by modeling it as a shortest path problem on a graph. The integers from 1 to 9999 are the graph's nodes. A directed edge exists from number `u` to `v` if `v` can be reached from `u` by a single valid digit operation. The cost of traversing this edge is defined in a way that accumulates the values of the nodes. We can then use a modified version of Dijkstra's algorithm to find the path from `n` to `m` with the minimum cumulative cost.
**Time:** O(D * V * log(V)), where V is the number of nodes (10000) and D is the number of digits (at most 4). For each node, we do O(D) work to find neighbors, and there are O(D*V) edges in total. Dijkstra with a priority queue gives this complexity. · **Space:** O(V), where V is the number of nodes (10000). This is for the `dist` array, the `isPrime` sieve array, and the priority queue, which can hold up to V elements in the worst case.
**Pros:** Guaranteed to find the optimal solution (minimum cost).; Efficient and will pass within the time limits for the given constraints.
**Cons:** More complex to implement than a simple DFS/BFS.; Requires careful handling of the non-standard cost definition, which dictates the relaxation step in the algorithm.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private boolean[] isPrime;
    private int numDigits;

    private void sieve(int max) {
        isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int p = 2; p * p <= max; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= max; i += p) {
                    isPrime[i] = false;
                }
            }
        }
    }

    private List<Integer> getNeighbors(int u) {
        List<Integer> neighbors = new ArrayList<>();
        char[] digits = String.valueOf(u).toCharArray();

        for (int i = 0; i < digits.length; i++) {
            char originalDigit = digits[i];
            
            // Increase digit
            if (originalDigit < '9') {
                digits[i]++;
                int v = Integer.parseInt(new String(digits));
                if (!isPrime[v]) {
                    neighbors.add(v);
                }
            }
            
            digits[i] = originalDigit; // Backtrack

            // Decrease digit
            if (originalDigit > '0') {
                if (i == 0 && numDigits > 1 && originalDigit == '1') {
                    // This would change the number of digits (e.g., 10 -> 0), so skip.
                } else {
                    digits[i]--;
                    int v = Integer.parseInt(new String(digits));
                    if (!isPrime[v]) {
                        neighbors.add(v);
                    }
                }
            }
            digits[i] = originalDigit; // Backtrack
        }
        return neighbors;
    }

    public int minimumCost(int n, int m) {
        if (n == m) {
            return 0;
        }
        
        sieve(9999);
        
        if (isPrime[n] || isPrime[m]) {
            return -1;
        }

        numDigits = String.valueOf(n).length();

        long[] dist = new long[10000];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[n] = n;

        // Priority Queue stores {cost, number}
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[0]));
        pq.offer(new long[]{n, n});

        while (!pq.isEmpty()) {
            long[] current = pq.poll();
            long currentCost = current[0];
            int u = (int) current[1];

            if (currentCost > dist[u]) {
                continue;
            }

            if (u == m) {
                return (int) dist[m];
            }

            for (int v : getNeighbors(u)) {
                if (dist[u] != Long.MAX_VALUE && dist[u] + v < dist[v]) {
                    dist[v] = dist[u] + v;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
- **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.

# Solutions
### Java

```java
class Solution {
private
  boolean[] sieve;
private
  void runSieve() {
    sieve = new boolean[100000];
    Arrays.fill(sieve, true);
    sieve[0] = false;
    sieve[1] = false;
    for (int i = 2; i < 100000; i++) {
      if (sieve[i]) {
        for (int j = 2 * i; j < 100000; j += i) {
          sieve[j] = false;
        }
      }
    }
  }
private
  int solve(int n, int m) {
    PriorityQueue<int[]> pq =
        new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    pq.add(new int[]{n, n});
    Set<Integer> visited = new HashSet<>();
    while (!pq.isEmpty()) {
      int[] top = pq.poll();
      int sum = top[0], cur = top[1];
      if (visited.contains(cur)) {
        continue;
      }
      visited.add(cur);
      if (cur == m) {
        return sum;
      }
      char[] s = String.valueOf(cur).toCharArray();
      for (int i = 0; i < s.length; i++) {
        char c = s[i];
        if (s[i] < '9') {
          s[i] = (char)(s[i] + 1);
          int next = Integer.parseInt(new String(s));
          if (!sieve[next] && !visited.contains(next)) {
            pq.add(new int[]{sum + next, next});
          }
          s[i] = c;
        }
        if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
          s[i] = (char)(s[i] - 1);
          int next = Integer.parseInt(new String(s));
          if (!sieve[next] && !visited.contains(next)) {
            pq.add(new int[]{sum + next, next});
          }
          s[i] = c;
        }
      }
    }
    return -1;
  }
public
  int minOperations(int n, int m) {
    runSieve();
    if (sieve[n] || sieve[m]) {
      return -1;
    }
    return solve(n, m);
  }
}

```

### CPP

```cpp
class Solution {
private:
  vector<bool> sieve;
  void runSieve() {
    sieve.resize(100000, true);
    sieve[0] = false, sieve[1] = false;
    for (int i = 2; i < 1e5; ++i) {
      if (sieve[i]) {
        for (int j = 2 * i; j < 1e5; j += i) {
          sieve[j] = false;
        }
      }
    }
  }
  int solve(int n, int m) {
    priority_queue<pair<int, int>, vector<pair<int, int>>,
                   greater<pair<int, int>>>
        pq;
    unordered_set<int> vis;
    pq.push({n, n});
    while (!pq.empty()) {
      int sum = pq.top().first, cur = pq.top().second;
      pq.pop();
      if (vis.find(cur) != vis.end())
        continue;
      vis.insert(cur);
      if (cur == m)
        return sum;
      string s = to_string(cur);
      for (int i = 0; i < s.size(); ++i) {
        char c = s[i];
        if (s[i] < '9') {
          s[i]++;
          int next = stoi(s);
          if (!sieve[next] && vis.find(next) == vis.end()) {
            pq.push({sum + next, next});
          }
          s[i] = c;
        }
        if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
          s[i]--;
          int next = stoi(s);
          if (!sieve[next] && vis.find(next) == vis.end()) {
            pq.push({sum + next, next});
          }
          s[i] = c;
        }
      }
    }
    return -1;
  }

public:
  int minOperations(int n, int m) {
    runSieve();
    if (sieve[n] || sieve[m])
      return -1;
    return solve(n, m);
  }
};

```

### Python

```python
import heapq class Solution : def __init__ ( self ): self . sieve = [] def run_sieve ( self ): self . sieve = [ True ] * 100000 self . sieve [ 0 ], self . sieve [ 1 ] = False , False for i in range ( 2 , 100000 ): if self . sieve [ i ]: for j in range ( 2 * i , 100000 , i ): self . sieve [ j ] = False def solve ( self , n , m ): pq = [] heapq . heappush ( pq , ( n , n )) visited = set () while pq : sum_ , cur = heapq . heappop ( pq ) if cur in visited : continue visited . add ( cur ) if cur == m : return sum_ s = list ( str ( cur )) for i in range ( len ( s )): c = s [ i ] if s [ i ] < '9' : s [ i ] = chr ( ord ( s [ i ]) + 1 ) next_ = int ( '' . join ( s )) if not self . sieve [ next_ ] and next_ not in visited : heapq . heappush ( pq , ( sum_ + next_ , next_ )) s [ i ] = c if s [ i ] > '0' and not ( i == 0 and s [ i ] == '1' ): s [ i ] = chr ( ord ( s [ i ]) - 1 ) next_ = int ( '' . join ( s )) if not self . sieve [ next_ ] and next_ not in visited : heapq . heappush ( pq , ( sum_ + next_ , next_ )) s [ i ] = c return - 1 def minOperations ( self , n , m ): self . run_sieve () if self . sieve [ n ] or self . sieve [ m ]: return - 1 return self . solve ( n , m )
```