Problem statement

You are given two integers n and m written with the same number of digits.

You may repeat either operation on n any number of times:

• pick a digit of n that is not 9 and increase it by 1;
• pick a digit of n that is not 0 and decrease it by 1.

n keeps its number of digits throughout — a leading digit may drop to 0, which simply makes the value smaller. The value of n must never be a prime number: not at the start, not after any operation, and not at the end.

The cost of a transformation is the sum of every value n takes, including its original value and its final value. Return the minimum cost to turn n into m, or -1 if it is impossible.

Example 1

Input: n = 10, m = 12
Output: 85
Explanation: 10 → 20 → 21 → 22 → 12 never visits a prime, and costs 10 + 20 + 21 + 22 + 12 = 85.

Example 2

Input: n = 4, m = 8
Output: -1
Explanation: Both neighbours of 4 (3 and 5) are prime, so `n` cannot move at all.

Example 3

Input: n = 6, m = 2
Output: -1
Explanation: The target 2 is prime.

Constraints

• 1 <= n, m < 10^4
• n and m consist of the same number of digits

Hints for Digit Operations to Make Two Integers Equal

1. Hint 1

   Think of every number with the same digit count as a node, and an operation as an edge to a number that differs by ±10^k.

2. Hint 2

   Entering a node costs its value, and the start counts too, so this is a shortest path with non-negative node weights: Dijkstra, starting with distance n.

3. Hint 3

   Sieve the primes below 10^d first, never enter a prime node, and return -1 up front if n or m is prime.

How to solve Digit Operations to Make Two Integers Equal

The states are the at most 10^d values with d digits, each operation is an edge, and the cost of a path is the sum of the node values on it. Dijkstra with "entering y costs y" finds the cheapest path.

Approach

1. Let d be the digit count of n. Sieve primality for 0 … 10^d - 1 (0 and 1 are not prime).
2. If n or m is prime, return -1.
3. Run Dijkstra from n with dist[n] = n. From x, for each position k with digit g: if g < 9, y = x + 10^k; if g > 0, y = x - 10^k. Skip prime y; relax dist[y] = dist[x] + y.
4. Return dist[m] when m is popped, or -1 if the heap empties first.

Why it works

All node weights are positive, so moving the weight onto the edge that enters a node gives a graph with positive edge weights, where Dijkstra is exact. Forbidding prime nodes enforces the "never prime" rule at every step, and counting n in the initial distance includes the original value.

Complexity

• Time — O(10^d · d · log(10^d))
• Space — O(10^d)

Pitfalls

• The original value and the final value both count in the cost.
• 1 is not prime, so a path may pass through it; 2 is prime.
• If n == m and it is not prime, the answer is n itself, not 0.

Reference solution

Python

import heapq

def minOperations(n: int, m: int) -> int:
    d = len(str(n))
    lim = 10 ** d
    sieve = [True] * lim
    sieve[0] = False
    if lim > 1:
        sieve[1] = False
    i = 2
    while i * i < lim:
        if sieve[i]:
            for j in range(i * i, lim, i):
                sieve[j] = False
        i += 1
    if sieve[n] or sieve[m]:
        return -1
    dist = [float("inf")] * lim
    dist[n] = n
    heap = [(n, n)]
    while heap:
        c, x = heapq.heappop(heap)
        if c > dist[x]:
            continue
        if x == m:
            return c
        p = 1
        for _ in range(d):
            g = (x // p) % 10
            for y in ((x + p) if g < 9 else -1, (x - p) if g > 0 else -1):
                if y >= 0 and not sieve[y] and c + y < dist[y]:
                    dist[y] = c + y
                    heapq.heappush(heap, (c + y, y))
            p *= 10
    return -1

Java

public static int minOperations(int n, int m) {
    int d = String.valueOf(n).length(), lim = 1;
    for (int i = 0; i < d; i++) lim *= 10;
    boolean[] prime = new boolean[lim];
    for (int i = 2; i < lim; i++) prime[i] = true;
    for (int i = 2; i * i < lim; i++) if (prime[i]) for (int j = i * i; j < lim; j += i) prime[j] = false;
    if (prime[n] || prime[m]) return -1;
    int[] dist = new int[lim];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[n] = n;
    PriorityQueue<long[]> heap = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    heap.add(new long[]{n, n});
    while (!heap.isEmpty()) {
        long[] top = heap.poll();
        int c = (int) top[0], x = (int) top[1];
        if (c > dist[x]) continue;
        if (x == m) return c;
        for (int k = 0, p = 1; k < d; k++, p *= 10) {
            int g = (x / p) % 10;
            int[] cands = {g < 9 ? x + p : -1, g > 0 ? x - p : -1};
            for (int y : cands) {
                if (y >= 0 && !prime[y] && c + y < dist[y]) { dist[y] = c + y; heap.add(new long[]{c + y, y}); }
            }
        }
    }
    return -1;
}

C++

int minOperations(int n, int m) {
    int d = to_string(n).size(), lim = 1;
    for (int i = 0; i < d; i++) lim *= 10;
    vector<bool> prime(lim, true);
    prime[0] = false;
    if (lim > 1) prime[1] = false;
    for (int i = 2; i * i < lim; i++) if (prime[i]) for (int j = i * i; j < lim; j += i) prime[j] = false;
    if (prime[n] || prime[m]) return -1;
    vector<int> dist(lim, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    dist[n] = n;
    heap.push(make_pair(n, n));
    while (!heap.empty()) {
        int c = heap.top().first, x = heap.top().second;
        heap.pop();
        if (c > dist[x]) continue;
        if (x == m) return c;
        for (int k = 0, p = 1; k < d; k++, p *= 10) {
            int g = (x / p) % 10;
            int cands[2] = {g < 9 ? x + p : -1, g > 0 ? x - p : -1};
            for (int y : cands) {
                if (y >= 0 && !prime[y] && c + y < dist[y]) { dist[y] = c + y; heap.push(make_pair(c + y, y)); }
            }
        }
    }
    return -1;
}

JavaScript

var minOperations = function(n, m) {
    var d = String(n).length, lim = 1, i, j;
    for (i = 0; i < d; i++) lim *= 10;
    var prime = [];
    for (i = 0; i < lim; i++) prime.push(i >= 2);
    for (i = 2; i * i < lim; i++) if (prime[i]) for (j = i * i; j < lim; j += i) prime[j] = false;
    if (prime[n] || prime[m]) return -1;
    var SH = 16384, dist = [];
    for (i = 0; i < lim; i++) dist.push(Infinity);
    dist[n] = n;
    var heap = [n * SH + n];
    while (heap.length > 0) {
        var key = heapPop(heap);
        var x = key % SH, c = (key - x) / SH;
        if (c > dist[x]) continue;
        if (x === m) return c;
        for (var p = 1, k = 0; k < d; k++, p *= 10) {
            var g = Math.floor(x / p) % 10;
            var cands = [g < 9 ? x + p : -1, g > 0 ? x - p : -1];
            for (var t = 0; t < 2; t++) {
                var y = cands[t];
                if (y >= 0 && !prime[y] && c + y < dist[y]) { dist[y] = c + y; heapPush(heap, (c + y) * SH + y); }
            }
        }
    }
    return -1;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More math problems

• Product of the Last K Numbers Medium
• Add 1 to a Number Represented as Linked List Medium
• Double a Number Represented as a Linked List Medium
• Insert Greatest Common Divisors in Linked List Medium
• Add Two Numbers II Medium
• Add Two Numbers Medium