Deloitte | COGNIZANT | IBM | CAPGEMINI
def transform_to_smallest_prime( input1, input2):
from collections import deque
N, K = str(input1), input2
n = len(N)
def is_prime(x):
if x < 2:
return False
if x % 2 == 0 and x != 2:
return False
d = 3
while d * d <= x:
if x % d == 0:
return False
d += 2
return True
q = deque([(N, 0)])
seen = {N: 0}
best_prime = None
while q:
cur, steps = q.popleft()
if steps <= K:
val = int(cur)
if cur[0] != '0' and is_prime(val):
if best_prime is None or val < best_prime:
best_prime = val
if steps < K:
for i in range(n):
d = int(cur[i])
for nd in [d - 1, d + 1]:
if 0 <= nd <= 9:
nxt = cur[:i] + str(nd) + cur[i+1:]
if nxt not in seen or seen[nxt] > steps + 1:
seen[nxt] = steps + 1
q.append((nxt, steps + 1))
return best_prime if best_prime is not None else -1
//prime transformation✅✅
VIRTUSA✅
682 ·