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 < 104n and m consist of the same number of digits.
Solutions
Solution 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
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)
}
|