Welcome to Subscribe On Youtube
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
nthat is not 9 and increase it by 1. - Choose any digit from
nthat 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 < 104nandmconsist of the same number of digits.
Solutions
Solution 1
-
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); } } -
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); } }; -
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) -
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) }