3655. Digit Operations to Make Two Integers Equal
My accepted Python solution to LeetCode problem 3655, Digit Operations to Make Two Integers Equal, running in 890ms.
- Difficulty: Medium
- Python
- Runtime 890ms
- Memory 18.5MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 890ms, memory 18.5MB, accepted 2025-12-31.
class Solution:
def minOperations(self, n: int, m: int) -> int:
import heapq
# Sieve of Eratosthenes for primes up to 10000
MAX_VAL = 10000
is_prime = [True] * MAX_VAL
is_prime[0] = is_prime[1] = False
for i in range(2, int(MAX_VAL**0.5) + 1):
if is_prime[i]:
for j in range(i*i, MAX_VAL, i):
is_prime[j] = False
# If n or m is prime, impossible
if is_prime[n] or is_prime[m]:
return -1
# Get number of digits
num_digits = len(str(n))
min_val = 10 ** (num_digits - 1) if num_digits > 1 else 0
max_val = 10 ** num_digits
# Dijkstra
dist = {n: n}
pq = [(n, n)] # (cost, current_value)
while pq:
cost, curr = heapq.heappop(pq)
if curr == m:
return cost
if cost > dist.get(curr, float('inf')):
continue
# Generate neighbors
s = list(str(curr))
for i in range(len(s)):
orig = s[i]
# Increase digit
if s[i] != '9':
s[i] = str(int(s[i]) + 1)
new_val = int(''.join(s))
if min_val <= new_val < max_val and not is_prime[new_val]:
new_cost = cost + new_val
if new_cost < dist.get(new_val, float('inf')):
dist[new_val] = new_cost
heapq.heappush(pq, (new_cost, new_val))
s[i] = orig
# Decrease digit
if s[i] != '0' and not (i == 0 and s[i] == '1' and len(s) > 1):
s[i] = str(int(s[i]) - 1)
new_val = int(''.join(s))
if min_val <= new_val < max_val and not is_prime[new_val]:
new_cost = cost + new_val
if new_cost < dist.get(new_val, float('inf')):
dist[new_val] = new_cost
heapq.heappush(pq, (new_cost, new_val))
s[i] = orig
return -1