Digit Operations to Make Two Integers Equal – Java Solution

Problem Description

So, you’ve got two integers, and you want to make them equal. Sounds simple, right? Well, welcome to the world of digit operations! Imagine you’re trying to convince your friend to share their pizza, but instead of just asking nicely, you have to change the toppings on your own slice to match theirs. That’s basically what this problem is about—changing the digits of one number to match another, but with a twist! You can only increase or decrease the digits one at a time, and oh, by the way, you can’t land on a prime number. Because who needs prime numbers in their life, right?

Code Solution


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 seen = new HashSet<>(Arrays.asList(src));
    Queue> 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;
  }
}

Approach Explanation

The solution employs Dijkstra's algorithm to find the minimum operations required to make two integers equal. It starts from the source integer and explores all possible digit changes (incrementing or decrementing each digit) while avoiding prime numbers. The algorithm uses a priority queue to always expand the least costly option first, ensuring that the shortest path to the destination integer is found efficiently.

Time and Space Complexity

Time Complexity: O(log(n) * 10^d), where d is the number of digits in the larger of the two integers. This is because for each digit, we can make at most 10 changes (0-9).
Space Complexity: O(n), where n is the maximum number of integers we might need to store in our priority queue and seen set.

Real-World Example

Imagine you’re at a party, and you want to match your drink to your friend’s. You can only change your drink one sip at a time, and you can’t choose any drink that’s considered “too fancy” (like a prime number drink). You keep sipping until your drink matches theirs. This is essentially what the algorithm does—step by step, it adjusts the digits of one number to match another while avoiding the “fancy” primes.