3377. Digit Operations to Make Two Integers Equal

MediumGraphMathNumber TheoryShortest PathHeap (Priority Queue)

Problem 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 n that is not 9 and increase it by 1.
Choose any digit from n that 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.

Intuition

The goal is to transform the integer n into m by adjusting its digits while ensuring that n never becomes a prime number during the process. Moreover, the transformation should be done in such a way that the total cost, defined as the sum of all values that n takes throughout the transformation, is minimized.

Here's how we can approach the problem:

Verify Non-Primality: Start by checking if either n or m is prime initially. If either is prime, return -1 immediately because it's impossible to start or end at a prime number.
Precompute Prime Numbers: Use the Sieve of Eratosthenes to precompute all prime numbers up to a large number (here, 100,000) to efficiently check primality as the digits of n are altered.
Breadth-First Search (BFS): Use a priority queue (min-heap) to explore all possible transformations of n. Each state in the queue consists of a tuple containing the current cost and the current value of n.
Transform and Explore: For each value of n, consider all possible digit transformations that either increase or decrease a digit within its range. Ensure that these transformations do not result in a prime number. Add these new states to the queue with the updated cost.
End Condition: The process continues until n is transformed into m. To achieve the minimum cost transformation, always prioritize states with lower cumulative costs due to the nature of the min-heap.
Impossible Transformation: If there is no path to transform n into m without turning n prime, return -1.

This approach effectively finds the least costly transformation by verifying non-primal transitions during digit changes, using a systematic BFS strategy aided by a precomputed sieve for primality checks.

Learn more about Graph, Math, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution implements an algorithm to transform the number n into m with the minimum cost under the given constraints. Here's a breakdown of how the implementation works:

Prime Number Precomputation: The solution begins with the run_sieve method, which uses the Sieve of Eratosthenes to precompute a list of prime numbers up to 100,000. This list, stored as self.sieve, allows for rapid primality checks.

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

Breadth-First Search Using a Priority Queue: The minOperations method initiates the search with a priority queue (pq). This queue is used to explore transformations of n, prioritizing paths with the lowest cumulative cost due to the use of a min-heap.

State Exploration: The priority queue is initialized with the starting number n, and its initial cost. The solve method contains the core logic that performs BFS to explore valid transformations:

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_
      
        # Transform each digit
        s = list(str(cur))
        for i in range(len(s)):
            c = s[i]

            # Increase digit if it's not 9
            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  # Revert

            # Decrease digit if it's not 0
            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  # Revert

    return -1

Digit Modification Rules: For each digit of the current number, the solution considers increasing it if it's not 9 and decreasing it if it's not 0, ensuring the number does not turn prime after each modification.
Termination and Result: The search concludes when n transforms into m. If successful transformations exist, the total cost is returned. If no valid transformation is possible, -1 is returned.

This approach leverages efficient primality checks and exploration strategies to achieve an optimal solution path while adhering to the constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's consider an example where n = 131 and m = 132.

Initial Check for Non-Primality:
- First, we check if n or m is a prime number. Both 131 and 132 are checked against our precomputed sieve. It turns out 131 is prime, so initial conditions make the transformation impossible.
- Consequently, we return -1 because the problem specifies that neither the original value nor any intermediate transformation of n can be prime.

Consider an example where transformations are possible:

Let n = 120 and m = 123.

Initialize the Priority Queue:
- Start with a priority queue initialized with the value 120 and its current cost (which is itself initially), i.e., (120, 120).
State Exploration and Transitions:
- Current n = 120. Check possible transformations:
  - Increase the rightmost digit 0 to 1. Gives 121, which is not prime and less than 123.
  - Push (241, 121) into the queue (241 is the cumulative cost 120 + 121).
Subsequent Steps:
- Explore 121:
  - Increase 1 at the end to 2. Gives 122.
  - Ensure 122 isn't prime and push (363, 122) into the queue (363 is 241 + 122).
- Explore 122:
  - Increase 2 at the end to 3. Results in 123.
  - Verify 123 isn't prime. Push (486, 123) into the queue (486 is 363 + 123).
Reach the Target m:
- We finally pop 123 from the queue, reaching our target number. The total minimal cost accumulated is 486.

This approach guarantees that we neither start nor transition into a prime, finding the sequence and corresponding cost that transforms n into m with minimal change along a non-prime path.

Solution Implementation

1import heapq
2
3class Solution:
4    def __init__(self):
5        # Initialize the sieve list that will be used for marking primes
6        self.sieve = []
7
8    def run_sieve(self):
9        # Create a list to mark non-prime numbers using the Sieve of Eratosthenes method
10        self.sieve = [True] * 100000
11        self.sieve[0], self.sieve[1] = False, False  # 0 and 1 are not prime numbers
12
13        # Iterate over each number to mark its multiples as non-prime
14        for i in range(2, 100000):
15            if self.sieve[i]:
16                # Mark all multiples of i as non-prime
17                for j in range(2 * i, 100000, i):
18                    self.sieve[j] = False
19
20    def solve(self, n, m):
21        # Priority queue for BFS
22        priority_queue = []
23      
24        # Start with the initial number n
25        heapq.heappush(priority_queue, (n, n))
26      
27        # Track visited numbers
28        visited = set()
29
30        while priority_queue:
31            # Pop the minimum sum value from the priority queue
32            sum_, current = heapq.heappop(priority_queue)
33
34            # Check if this number has already been visited
35            if current in visited:
36                continue
37            visited.add(current)
38
39            # Check if we have reached the target number m
40            if current == m:
41                return sum_
42
43            # Convert the current number to a list of characters for manipulation
44            str_num = list(str(current))
45            for i in range(len(str_num)):
46                original_digit = str_num[i]
47
48                # Try increasing the current digit
49                if str_num[i] < '9':
50                    # Increase by one
51                    str_num[i] = chr(ord(str_num[i]) + 1)
52                    next_number = int(''.join(str_num))
53                  
54                    # If the next number is not prime and not visited, add it to the priority queue
55                    if not self.sieve[next_number] and next_number not in visited:
56                        heapq.heappush(priority_queue, (sum_ + next_number, next_number))
57                  
58                    # Revert back to the original digit
59                    str_num[i] = original_digit
60
61                # Try decreasing the current digit
62                if str_num[i] > '0' and not (i == 0 and str_num[i] == '1'):
63                    # Decrease by one
64                    str_num[i] = chr(ord(str_num[i]) - 1)
65                    next_number = int(''.join(str_num))
66                  
67                    # If the next number is not prime and not visited, add it to the priority queue
68                    if not self.sieve[next_number] and next_number not in visited:
69                        heapq.heappush(priority_queue, (sum_ + next_number, next_number))
70                  
71                    # Revert back to the original digit
72                    str_num[i] = original_digit
73
74        # Return -1 if no transformation is possible from n to m
75        return -1
76
77    def minOperations(self, n, m):
78        # Generate the sieve for prime numbers up to 100,000
79        self.run_sieve()
80      
81        # If either input number is prime, return -1 as operations can't start from or reach a prime
82        if self.sieve[n] or self.sieve[m]:
83            return -1
84      
85        # Use a BFS-based solution to find the minimum operations from n to m
86        return self.solve(n, m)
87

1import java.util.*;
2
3class Solution {
4    private boolean[] sieve;
5  
6    // Method to initialize the sieve of Eratosthenes
7    private void runSieve() {
8        sieve = new boolean[100000];
9      
10        // Assume all numbers are prime initially
11        Arrays.fill(sieve, true);
12      
13        // 0 and 1 are not prime numbers
14        sieve[0] = false;
15        sieve[1] = false;
16      
17        // Sieve of Eratosthenes algorithm to mark non-prime numbers
18        for (int i = 2; i < 100000; i++) {
19            if (sieve[i]) {
20                // Mark all multiples of i as non-prime
21                for (int j = 2 * i; j < 100000; j += i) {
22                    sieve[j] = false;
23                }
24            }
25        }
26    }
27  
28    // Method to solve the problem of transforming n to m with minimum operations
29    private int solve(int n, int m) {
30        // Priority queue to store pairs of sum and current number, sorted by sum
31        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
32      
33        // Add the initial number with its sum
34        priorityQueue.add(new int[] {n, n});
35      
36        // Set to keep track of visited numbers
37        Set<Integer> visited = new HashSet<>();
38      
39        while (!priorityQueue.isEmpty()) {
40            // Retrieve the top element in the priority queue
41            int[] top = priorityQueue.poll();
42            int sum = top[0], current = top[1];
43          
44            // Skip the number if it has been visited
45            if (visited.contains(current)) {
46                continue;
47            }
48          
49            // Mark the current number as visited
50            visited.add(current);
51
52            // If we have reached the target number, return the sum
53            if (current == m) {
54                return sum;
55            }
56
57            char[] digits = String.valueOf(current).toCharArray();
58          
59            // Iterate through each digit to attempt a change
60            for (int i = 0; i < digits.length; i++) {
61                char original = digits[i];
62
63                // Try increasing the digit if possible
64                if (digits[i] < '9') {
65                    digits[i] = (char) (digits[i] + 1);
66                    int nextNumber = Integer.parseInt(new String(digits));
67                    if (!sieve[nextNumber] && !visited.contains(nextNumber)) {
68                        priorityQueue.add(new int[] {sum + nextNumber, nextNumber});
69                    }
70                    // Revert the digit change
71                    digits[i] = original;
72                }
73
74                // Try decreasing the digit if possible
75                if (digits[i] > '0' && !(i == 0 && digits[i] == '1')) {
76                    digits[i] = (char) (digits[i] - 1);
77                    int nextNumber = Integer.parseInt(new String(digits));
78                    if (!sieve[nextNumber] && !visited.contains(nextNumber)) {
79                        priorityQueue.add(new int[] {sum + nextNumber, nextNumber});
80                    }
81                    // Revert the digit change
82                    digits[i] = original;
83                }
84            }
85        }
86      
87        // Return -1 if there is no possible way to reach m from n
88        return -1;
89    }
90  
91    // Public method to calculate the minimum operations
92    public int minOperations(int n, int m) {
93        runSieve();
94      
95        // If either n or m is a prime number, return -1
96        if (sieve[n] || sieve[m]) {
97            return -1;
98        }
99      
100        return solve(n, m);
101    }
102}
103

1#include <vector>
2#include <queue>
3#include <unordered_set>
4#include <string>
5#include <utility>
6
7using namespace std;
8
9class Solution {
10private:
11    vector<bool> sieve; // Sieve of Eratosthenes container to identify prime numbers.
12
13    // Method to execute the Sieve of Eratosthenes algorithm.
14    void runSieve() {
15        // Initialize sieve vector with true, indicating potential prime status.
16        sieve.resize(100000, true);
17        // 0 and 1 are not prime numbers.
18        sieve[0] = false;
19        sieve[1] = false;
20      
21        // Begin marking non-prime numbers.
22        for (int i = 2; i < 100000; ++i) {
23            if (sieve[i]) { // If i is a prime,
24                // Mark all multiples of i as non-prime.
25                for (int j = 2 * i; j < 100000; j += i) {
26                    sieve[j] = false;
27                }
28            }
29        }
30    }
31
32    // Function to solve the problem using a priority queue for minimum cost pathfinding.
33    int solve(int n, int m) {
34        // Min-heap priority queue to explore paths with the smallest current sum.
35        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
36        unordered_set<int> vis; // Set to track visited numbers.
37      
38        // Initialize the queue with starting number 'n' and its sum.
39        pq.push({n, n});
40
41        // While there are paths to explore
42        while (!pq.empty()) {
43            int sum = pq.top().first; // Current sum
44            int cur = pq.top().second; // Current number
45            pq.pop();
46          
47            // Skip already visited numbers.
48            if (vis.find(cur) != vis.end()) continue;
49          
50            // Mark number as visited.
51            vis.insert(cur);
52          
53            // If the current number matches the target, return the accumulated sum.
54            if (cur == m) return sum;
55          
56            string s = to_string(cur);
57            // Create neighbors by modifying one digit at a time.
58            for (int i = 0; i < s.size(); ++i) {
59                char c = s[i];
60
61                // Increment digit if it's less than 9.
62                if (s[i] < '9') {
63                    s[i]++;
64                    int next = stoi(s);
65                    // Push valid new numbers if they're not visited and not prime.
66                    if (!sieve[next] && vis.find(next) == vis.end()) {
67                        pq.push({sum + next, next});
68                    }
69                    s[i] = c; // Restore original digit
70                }
71
72                // Decrement digit if it's greater than 0 and not leading to number 0.
73                if (s[i] > '0' && !(i == 0 && s[i] == '1')) {
74                    s[i]--;
75                    int next = stoi(s);
76                    // Push valid new numbers if they're not visited and not prime.
77                    if (!sieve[next] && vis.find(next) == vis.end()) {
78                        pq.push({sum + next, next});
79                    }
80                    s[i] = c; // Restore original digit
81                }
82            }
83        }
84
85        // Return -1 if no valid path is found.
86        return -1;
87    }
88
89public:
90    // Main function to determine minimum path sum between two numbers.
91    int minOperations(int n, int m) {
92        runSieve(); // Run the Sieve of Eratosthenes.
93
94        // Immediately return -1 if either number is prime.
95        if (sieve[n] || sieve[m]) return -1;
96      
97        // Call the solver function to compute the result.
98        return solve(n, m);
99    }
100};
101

1// Define a sieve array to determine prime numbers (Sieve of Eratosthenes).
2let sieve: boolean[] = [];
3
4// Function to execute the Sieve of Eratosthenes algorithm.
5function runSieve() {
6    // Initialize the sieve array with true values, suggesting all numbers are prime.
7    sieve = new Array(100000).fill(true);
8
9    // 0 and 1 are not prime numbers.
10    sieve[0] = false;
11    sieve[1] = false;
12
13    // Start marking non-prime numbers.
14    for (let i = 2; i < 100000; i++) {
15        if (sieve[i]) { // If i remains true, it's a prime.
16            // Mark multiples of i as false (non-prime).
17            for (let j = 2 * i; j < 100000; j += i) {
18                sieve[j] = false;
19            }
20        }
21    }
22}
23
24// Function to find the minimum path sum using a priority queue (min-heap).
25function solve(n: number, m: number): number {
26    // Priority queue to explore paths prioritized by the smallest current sum.
27    const pq: Array<[number, number]> = [];
28    const vis: Set<number> = new Set(); // Set to track visited numbers.
29
30    // Initialize the queue with the starting number and its sum.
31    pq.push([n, n]);
32
33    // Process paths until there are no more to explore.
34    while (pq.length > 0) {
35        // Extract the path with the minimum sum.
36        pq.sort((a, b) => a[0] - b[0]); // Sort to act as a min-heap.
37        const [sum, cur] = pq.shift()!;
38
39        // Skip numbers that have already been visited.
40        if (vis.has(cur)) continue;
41
42        // Mark the number as visited.
43        vis.add(cur);
44
45        // If the current number matches the target, return the accumulated sum.
46        if (cur === m) return sum;
47
48        const s = cur.toString();
49        // Explore neighboring numbers by changing each digit.
50        for (let i = 0; i < s.length; i++) {
51            const c = s[i];
52
53            // Increment the digit if it's less than 9.
54            if (s[i] < '9') {
55                const incremented = s.substring(0, i) + (parseInt(s[i]) + 1) + s.substring(i + 1);
56                const next = parseInt(incremented);
57                // Add valid unvisited and non-prime numbers to the queue.
58                if (!sieve[next] && !vis.has(next)) {
59                    pq.push([sum + next, next]);
60                }
61            }
62
63            // Decrement the digit if it's greater than 0 and not leading to number 0.
64            if (s[i] > '0' && !(i === 0 && s[i] === '1')) {
65                const decremented = s.substring(0, i) + (parseInt(s[i]) - 1) + s.substring(i + 1);
66                const next = parseInt(decremented);
67                // Add valid unvisited and non-prime numbers to the queue.
68                if (!sieve[next] && !vis.has(next)) {
69                    pq.push([sum + next, next]);
70                }
71            }
72        }
73    }
74
75    // Return -1 if no valid path is found.
76    return -1;
77}
78
79// Main function to determine the minimum path sum between two numbers.
80function minOperations(n: number, m: number): number {
81    runSieve(); // Execute the Sieve of Eratosthenes.
82
83    // Return -1 immediately if either number is prime.
84    if (sieve[n] || sieve[m]) return -1;
85
86    // Use the solver function to compute and return the result.
87    return solve(n, m);
88}
89

Time and Space Complexity

The code primarily consists of two parts: the run_sieve method and the solve method. Let's analyze each part:

run_sieve Method:
- Time Complexity: The method uses the Sieve of Eratosthenes to determine primes up to 100,000. The time complexity of this sieve is O(n log log n), where n is 100,000 in this case.
- Space Complexity: The space used by the sieve is O(n), where n is 100,000, due to the boolean array self.sieve.
solve Method:
- Time Complexity: This uses a priority queue (min-heap) and a breadth-first search (BFS) like approach for transformations. The complexity depends on the number of states and potential operations, but it is approximately O(N * D), where N is the value range (up to 100,000) and D is the number of digits involved, limited operations per state due to numerical transformations.
- Space Complexity: The use of a priority queue and a visited set could take up to O(N) space in the worst case, where N is constrained by possible numbers.

Overall, the computational complexity is dominated by the BFS and priority queue operations related to the range of numbers and the digits involved in transformations.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which type of traversal does breadth first search do?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don’t know