#3377

Medium

LeetCode Problem Workspace

Digit Operations to Make Two Integers Equal

Transform n into m using allowed digit operations without creating primes, applying math and graph strategies efficiently.

math graph heap priority queue number theory shortest path

Problem Statement

You are given two integers n and m of equal digit length. You may perform operations on n to transform it digit by digit, but n must never be prime during the process. Each operation has a defined cost, and your goal is to make n equal to m using the minimum total cost.

Operations can be repeated any number of times as long as the intermediate numbers are non-prime. If it is impossible to transform n into m under these rules, return -1. You must consider all valid paths through the space of numbers, making this a combination of number theory, graph traversal, and priority queue management.

Examples

Example 1

Input: n = 10, m = 12

Output: 85

We perform the following operations:

Example 2

Input: n = 4, m = 8

Output: -1

It is impossible to make n equal to m .

Example 3

Input: n = 6, m = 2

Output: -1

Since 2 is already a prime, we can't make n equal to m .

Constraints

1 <= n, m < 104
n and m consist of the same number of digits.

Solution Approach

Graph Modeling

Treat each integer as a node and each allowed digit operation as a directed, weighted edge. Build a graph where edges only exist to non-prime numbers, representing all valid transitions from n to potential numbers.

Shortest Path Search

Use a priority queue to perform Dijkstra-like traversal of the graph. Always expand the node with the lowest accumulated cost, updating distances to reachable numbers until reaching m or exhausting possibilities.

Prime Checking Constraint

Integrate a fast primality check for each number before adding it to the graph or queue. Skip any operation that produces a prime, ensuring the non-prime restriction is never violated.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of valid non-prime numbers and edges in the graph, roughly O(V log V + E) with priority queue operations. Space complexity is determined by storing visited nodes and the priority queue.

What Interviewers Usually Probe

Expect a graph modeling approach connecting numbers via allowed operations.
Watch for failure to enforce non-prime constraint after each operation.
Use a heap to optimize shortest-path computation and minimize total cost.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check primality after each operation, leading to invalid paths.
Mismanaging the priority queue, which may produce non-optimal solutions.
Assuming all digit transformations are valid without constraints on intermediate primes.

Follow-up variants

Allow transformations even if n temporarily becomes prime, changing graph connectivity.
Introduce different cost metrics for operations, requiring weighted graph adjustments.
Limit the number of allowed operations, transforming the problem into a bounded shortest path challenge.

FAQ

What is the main pattern behind Digit Operations to Make Two Integers Equal?

The problem combines Math and Graph patterns, modeling numbers as graph nodes and operations as edges while avoiding primes.

Can n ever become prime during operations?

No, n must remain non-prime throughout all intermediate steps and at the start.

Why use a priority queue for this problem?

A priority queue ensures you always expand the path with the lowest accumulated cost, similar to Dijkstra's algorithm.

What should I do if no valid transformations exist?

Return -1 when it is impossible to transform n into m without violating the non-prime constraint.

How do digit operations affect graph construction?

Each digit operation creates a directed edge to a new non-prime number, forming the graph that represents all valid transformations.

terminal

Solution

Solution 1

#### Python3

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)

Continue Practicing

#3342 find minimum time to reach last room ii #3341 find minimum time to reach last room i #3286 find a safe walk through a grid