Skip to content

3377. Digit Operations to Make Two Integers Equal

Description

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.

Solutions

Solution 1

Thinking

We may increment or decrement one digit (no leading zero) and must avoid primes. The cost is the sum of visited values from \(n\) to \(m\). Values stay below \(10^4\), so this is a shortest path on an implicit graph.

Sieve primes up to \(10^5\). If \(n\) or \(m\) is prime there is no path. Each digit \(\pm 1\) is an edge whose weight is the newly reached number.

Dijkstra on the running sum pops \(m\) with the minimum total.

 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
51
52
53
54
import heapq

class Solution:
    def __init__(self):
        self.sieve = []

    def run_sieve(self):
        self.sieve = [True] * 100000
        self.sieve[0], self.sieve[1] = False, False
        for i in range(2, 100000):
            if self.sieve[i]:
                for j in range(2 * i, 100000, i):
                    self.sieve[j] = False

    def solve(self, n, m):
        pq = []
        heapq.heappush(pq, (n, n))
        visited = set()

        while pq:
            sum_, cur = heapq.heappop(pq)

            if cur in visited:
                continue
            visited.add(cur)

            if cur == m:
                return sum_

            s = list(str(cur))
            for i in range(len(s)):
                c = s[i]

                if s[i] < '9':
                    s[i] = chr(ord(s[i]) + 1)
                    next_ = int(''.join(s))
                    if not self.sieve[next_] and next_ not in visited:
                        heapq.heappush(pq, (sum_ + next_, next_))
                    s[i] = c

                if s[i] > '0' and not (i == 0 and s[i] == '1'):
                    s[i] = chr(ord(s[i]) - 1)
                    next_ = int(''.join(s))
                    if not self.sieve[next_] and next_ not in visited:
                        heapq.heappush(pq, (sum_ + next_, next_))
                    s[i] = c

        return -1

    def minOperations(self, n, m):
        self.run_sieve()
        if self.sieve[n] or self.sieve[m]:
            return -1
        return self.solve(n, m)

 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
    private boolean[] sieve;

    private void runSieve() {
        sieve = new boolean[100000];
        Arrays.fill(sieve, true);
        sieve[0] = false;
        sieve[1] = false;
        for (int i = 2; i < 100000; i++) {
            if (sieve[i]) {
                for (int j = 2 * i; j < 100000; j += i) {
                    sieve[j] = false;
                }
            }
        }
    }

    private int solve(int n, int m) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        pq.add(new int[] {n, n});
        Set<Integer> visited = new HashSet<>();

        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int sum = top[0], cur = top[1];

            if (visited.contains(cur)) {
                continue;
            }
            visited.add(cur);

            if (cur == m) {
                return sum;
            }

            char[] s = String.valueOf(cur).toCharArray();
            for (int i = 0; i < s.length; i++) {
                char c = s[i];

                if (s[i] < '9') {
                    s[i] = (char) (s[i] + 1);
                    int next = Integer.parseInt(new String(s));
                    if (!sieve[next] && !visited.contains(next)) {
                        pq.add(new int[] {sum + next, next});
                    }
                    s[i] = c;
                }

                if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
                    s[i] = (char) (s[i] - 1);
                    int next = Integer.parseInt(new String(s));
                    if (!sieve[next] && !visited.contains(next)) {
                        pq.add(new int[] {sum + next, next});
                    }
                    s[i] = c;
                }
            }
        }

        return -1;
    }

    public int minOperations(int n, int m) {
        runSieve();
        if (sieve[n] || sieve[m]) {
            return -1;
        }
        return solve(n, m);
    }
}

 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
51
52
53
54
55
class Solution {
private:
    vector<bool> sieve;
    void runSieve() {
        sieve.resize(100000, true);
        sieve[0] = false, sieve[1] = false;
        for (int i = 2; i < 1e5; ++i) {
            if (sieve[i]) {
                for (int j = 2 * i; j < 1e5; j += i) {
                    sieve[j] = false;
                }
            }
        }
    }
    int solve(int n, int m) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        unordered_set<int> vis;
        pq.push({n, n});
        while (!pq.empty()) {
            int sum = pq.top().first, cur = pq.top().second;
            pq.pop();
            if (vis.find(cur) != vis.end()) continue;
            vis.insert(cur);
            if (cur == m) return sum;
            string s = to_string(cur);
            for (int i = 0; i < s.size(); ++i) {
                char c = s[i];
                if (s[i] < '9') {
                    s[i]++;
                    int next = stoi(s);
                    if (!sieve[next] && vis.find(next) == vis.end()) {
                        pq.push({sum + next, next});
                    }
                    s[i] = c;
                }
                if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
                    s[i]--;
                    int next = stoi(s);
                    if (!sieve[next] && vis.find(next) == vis.end()) {
                        pq.push({sum + next, next});
                    }
                    s[i] = c;
                }
            }
        }
        return -1;
    }

public:
    int minOperations(int n, int m) {
        runSieve();
        if (sieve[n] || sieve[m]) return -1;
        return solve(n, m);
    }
};

 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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package main

import (
    "container/heap"
    "strconv"
)

type MinHeap [][]int

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.([]int))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

var sieve []bool

func runSieve() {
    sieve = make([]bool, 100000)
    for i := range sieve {
        sieve[i] = true
    }
    sieve[0], sieve[1] = false, false
    for i := 2; i < 100000; i++ {
        if sieve[i] {
            for j := 2 * i; j < 100000; j += i {
                sieve[j] = false
            }
        }
    }
}

func solve(n int, m int) int {
    pq := &MinHeap{}
    heap.Init(pq)
    heap.Push(pq, []int{n, n})
    visited := make(map[int]bool)

    for pq.Len() > 0 {
        top := heap.Pop(pq).([]int)
        sum, cur := top[0], top[1]

        if visited[cur] {
            continue
        }
        visited[cur] = true

        if cur == m {
            return sum
        }

        s := []rune(strconv.Itoa(cur))
        for i := 0; i < len(s); i++ {
            c := s[i]

            if s[i] < '9' {
                s[i]++
                next, _ := strconv.Atoi(string(s))
                if !sieve[next] && !visited[next] {
                    heap.Push(pq, []int{sum + next, next})
                }
                s[i] = c
            }

            if s[i] > '0' && !(i == 0 && s[i] == '1') {
                s[i]--
                next, _ := strconv.Atoi(string(s))
                if !sieve[next] && !visited[next] {
                    heap.Push(pq, []int{sum + next, next})
                }
                s[i] = c
            }
        }
    }

    return -1
}

func minOperations(n int, m int) int {
    runSieve()
    if sieve[n] || sieve[m] {
        return -1
    }
    return solve(n, m)
}

Comments