3377. Digit Operations to Make Two Integers Equal

• Time: $O(10^4\log 10^4 + |\texttt{digits}|\log |\texttt{digits}|)$
• Space: $O(10^4 + |\texttt{digits}|)$

C++JavaPython

class Solution {
 public:
  int minOperations(int n, int m) {
    constexpr int kMax = 10000;
    const vector<bool> isPrime = sieveEratosthenes(kMax);
    if (isPrime[n] || isPrime[m])
      return -1;
    return dijkstra(n, m, isPrime);
  }

 private:
  int dijkstra(int src, int dst, const vector<bool>& isPrime) {
    unordered_set<int> seen{src};
    using P = tuple<int, int>;  // (cost, num)
    priority_queue<P, vector<P>, greater<>> minHeap;
    minHeap.emplace(src, src);

    while (!minHeap.empty()) {
      const auto [cost, curr] = minHeap.top();
      minHeap.pop();
      if (curr == dst)
        return cost;
      string s = to_string(curr);
      for (int i = 0; i < s.length(); ++i) {
        if (s[i] < '9') {
          ++s[i];
          const int next = stoi(s);
          if (!isPrime[next] && !seen.contains(next)) {
            minHeap.emplace(cost + next, next);
            seen.insert(next);
          }
          --s[i];
        }
        if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
          --s[i];
          const int next = stoi(s);
          if (!isPrime[next] && !seen.contains(next)) {
            minHeap.emplace(cost + next, next);
            seen.insert(next);
          }
          ++s[i];
        }
      }
    }

    return -1;
  }

  vector<bool> sieveEratosthenes(int n) {
    vector<bool> isPrime(n, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i < n; ++i)
      if (isPrime[i])
        for (int j = i * i; j < n; j += i)
          isPrime[j] = false;
    return isPrime;
  }
};

class Solution {
  public int minOperations(int n, int m) {
    final int MAX = 10000;
    boolean[] isPrime = sieveEratosthenes(MAX);
    if (isPrime[n] || isPrime[m])
      return -1;
    return dijkstra(n, m, isPrime);
  }

  private int dijkstra(int src, int dst, boolean[] isPrime) {
    Set<Integer> seen = new HashSet<>(Arrays.asList(src));
    // (cost, num)
    Queue<Pair<Integer, Integer>> minHeap =
        new PriorityQueue<>(Comparator.comparingInt(Pair::getKey));
    minHeap.offer(new Pair<>(src, src));

    while (!minHeap.isEmpty()) {
      final int cost = minHeap.peek().getKey();
      final int curr = minHeap.poll().getValue();
      if (curr == dst)
        return cost;
      final String s = Integer.toString(curr);
      for (int i = 0; i < s.length(); ++i) {
        char[] chars = s.toCharArray();
        if (chars[i] < '9') {
          ++chars[i];
          final int next = Integer.parseInt(new String(chars));
          if (!isPrime[next] && !seen.contains(next)) {
            minHeap.offer(new Pair<>(cost + next, next));
            seen.add(next);
          }
          --chars[i];
        }
        if (chars[i] > '0' && !(i == 0 && chars[i] == '1')) {
          --chars[i];
          final int next = Integer.parseInt(new String(chars));
          if (!isPrime[next] && !seen.contains(next)) {
            minHeap.offer(new Pair<>(cost + next, next));
            seen.add(next);
          }
        }
      }
    }

    return -1;
  }

  private boolean[] sieveEratosthenes(int n) {
    boolean[] isPrime = new boolean[n];
    Arrays.fill(isPrime, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for (int i = 2; i * i < n; ++i)
      if (isPrime[i])
        for (int j = i * i; j < n; j += i)
          isPrime[j] = false;
    return isPrime;
  }
}

class Solution:
  def minOperations(self, n: int, m: int) -> int:
    isPrime = self._sieveEratosthenes(10000)
    if isPrime[n] or isPrime[m]:
      return -1
    return self._dijkstra(n, m, isPrime)

  def _dijkstra(self, src: int, dst: int, isPrime: list[bool]) -> int:
    seen = {src}
    minHeap = [(src, src)]  # (cost, num)

    while minHeap:
      cost, curr = heapq.heappop(minHeap)
      if curr == dst:
        return cost
      s = list(str(curr))
      for i, c in enumerate(s):
        if c < '9':
          s[i] = str(int(c) + 1)
          nextNum = int(''.join(s))
          if not isPrime[nextNum] and nextNum not in seen:
            heapq.heappush(minHeap, (cost + nextNum, nextNum))
            seen.add(nextNum)
          s[i] = c
        if c > '0' and not (i == 0 and c == '1'):
          s[i] = str(int(c) - 1)
          nextNum = int(''.join(s))
          if not isPrime[nextNum] and nextNum not in seen:
            heapq.heappush(minHeap, (cost + nextNum, nextNum))
            seen.add(nextNum)
          s[i] = c

    return -1

  def _sieveEratosthenes(self, n: int) -> list[bool]:
    isPrime = [True] * n
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, int(n**0.5) + 1):
      if isPrime[i]:
        for j in range(i * i, n, i):
          isPrime[j] = False
    return isPrime