Input: 10, m =12Output: 85Explanation:
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`.
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.
import heapq
classSolution:
defis_prime(self, x: int) -> bool:
if x <2:
returnFalsefor i in range(2, int(x **0.5) +1):
if x % i ==0:
returnFalsereturnTruedefdigit_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
defminimumCost(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:
continueif len(str(nx)) != len(sn):
continueif self.is_prime(nx):
continue heapq.heappush(heap, (cost + nx, nx))
return-1
⏰ 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.