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

1
2
3
4
5
6
7
8

Input: 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

1
2
3
4

Input: 4, m = 8
Output: -1
Explanation:
It is impossible to make `n` equal to `m`.

Example 3

1
2
3
4

Input: 6, m = 2
Output: -1
Explanation:
Since 2 is already a prime, we can't make `n` equal to `m`.

Constraints

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

Examples

Solution

Method 1 – Dijkstra’s Algorithm with Digit Operations

Intuition

We can treat each valid non-prime number as a node in a graph, and each allowed digit operation as an edge to another node. The cost of a path is the sum of all numbers visited. We want the minimum cost path from n to m where all intermediate numbers are non-prime.

Approach

  1. Use Dijkstra’s algorithm to find the minimum cost path from n to m.
  2. For each number, generate all possible numbers by increasing or decreasing any digit (not 9 for increase, not 0 for decrease).
  3. Skip numbers that are prime or have a different number of digits.
  4. Use a priority queue to always expand the lowest cost path.
  5. If m is reached, return the cost. If not possible, return -1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import heapq

class Solution:
    def is_prime(self, x: int) -> bool:
        if x < 2:
            return False
        for i in range(2, int(x ** 0.5) + 1):
            if x % i == 0:
                return False
        return True

    def digit_neighbors(self, x: int) -> list[int]:
        s = list(str(x))
        res = []
        for i, ch in enumerate(s):
            d = int(ch)
            if d < 9:
                ns = s[:]
                ns[i] = str(d + 1)
                res.append(int(''.join(ns)))
            if d > 0:
                ns = s[:]
                ns[i] = str(d - 1)
                res.append(int(''.join(ns)))
        return res

    def minimumCost(self, n: int, m: int) -> int:
        if self.is_prime(n) or self.is_prime(m):
            return -1
        sn, sm = str(n), str(m)
        if len(sn) != len(sm):
            return -1
        seen = set()
        heap = [(n, n)]  # (cost, value)
        while heap:
            cost, x = heapq.heappop(heap)
            if x == m:
                return cost
            if x in seen:
                continue
            seen.add(x)
            for nx in self.digit_neighbors(x):
                if nx in seen:
                    continue
                if len(str(nx)) != len(sn):
                    continue
                if self.is_prime(nx):
                    continue
                heapq.heappush(heap, (cost + nx, nx))
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.util.*;
class Solution {
    boolean isPrime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; ++i) if (x % i == 0) return false;
        return true;
    }
    List<Integer> digitNeighbors(int x, int len) {
        char[] s = Integer.toString(x).toCharArray();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < s.length; ++i) {
            int d = s[i] - '0';
            if (d < 9) {
                char[] ns = s.clone();
                ns[i] = (char)(d + 1 + '0');
                res.add(Integer.parseInt(new String(ns)));
            }
            if (d > 0) {
                char[] ns = s.clone();
                ns[i] = (char)(d - 1 + '0');
                res.add(Integer.parseInt(new String(ns)));
            }
        }
        return res;
    }
    public int minimumCost(int n, int m) {
        if (isPrime(n) || isPrime(m)) return -1;
        String sn = Integer.toString(n), sm = Integer.toString(m);
        if (sn.length() != sm.length()) return -1;
        Set<Integer> seen = new HashSet<>();
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.offer(new int[]{n, n});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int cost = cur[0], x = cur[1];
            if (x == m) return cost;
            if (!seen.add(x)) continue;
            for (int nx : digitNeighbors(x, sn.length())) {
                if (seen.contains(nx)) continue;
                if (Integer.toString(nx).length() != sn.length()) continue;
                if (isPrime(nx)) continue;
                pq.offer(new int[]{cost + nx, nx});
            }
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(10^d * d^2), where d is the number of digits (since each number can have up to 2d neighbors and we may visit all non-prime numbers of that length).
  • 🧺 Space complexity: O(10^d), for the visited set and priority queue.