3377. Digit Operations to Make Two Integers Equal LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3377. Digit Operations to Make Two Integers Equal LeetCode Solution with the best time and space complexity. The solution to Digit Operations to Make Two Integers Equal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Digit Operations to Make Two Integers Equal solution in C++
  4. Digit Operations to Make Two Integers Equal solution in Java
  5. Digit Operations to Make Two Integers Equal solution in Python
  6. Additional Resources
3377. Digit Operations to Make Two Integers Equal LeetCode Solution image

Problem Statement of Digit Operations to Make Two Integers Equal

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 = 20.
Increase the second digit, now n = 21.
Increase the second digit, now n = 22.
Decrease the first digit, now n = 12.

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.

Complexity Analysis

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

3377. Digit Operations to Make Two Integers Equal LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

3377. Digit Operations to Make Two Integers Equal LeetCode Solution in Java

class Solution {
  public int minOperations(int n, int m) {
    final int kMax = 10000;
    boolean[] isPrime = sieveEratosthenes(kMax);
    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.comparing(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;
  }
}
// code provided by PROGIEZ

3377. Digit Operations to Make Two Integers Equal LeetCode Solution in Python

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
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.