LeetCode-in-Java
3377. Digit Operations to Make Two Integers Equal
Medium
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
nthat is not 9 and increase it by 1. - Choose any digit from
nthat 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.
A prime number is a natural number greater than 1 with only two factors, 1 and itself.
Example 1:
Input: n = 10, m = 12
Output: 85
Explanation:
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.
Example 2:
Input: n = 4, m = 8
Output: -1
Explanation:
It is impossible to make n equal to m.
Example 3:
Input: n = 6, m = 2
Output: -1
Explanation:
Since 2 is already a prime, we can’t make n equal to m.
Constraints:
1 <= n, m < 104nandmconsist of the same number of digits.
Solution
import java.util.Arrays;
import java.util.PriorityQueue;
public class Solution {
public int minOperations(int n, int m) {
int limit = 100000;
boolean[] sieve = new boolean[limit + 1];
boolean[] visited = new boolean[limit];
Arrays.fill(sieve, true);
sieve[0] = false;
sieve[1] = false;
for (int i = 2; i * i <= limit; i++) {
if (sieve[i]) {
for (int j = i * i; j <= limit; j += i) {
sieve[j] = false;
}
}
}
if (sieve[n]) {
return -1;
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
visited[n] = true;
pq.add(new int[] {n, n});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int cost = current[0];
int num = current[1];
char[] temp = Integer.toString(num).toCharArray();
if (num == m) {
return cost;
}
for (int j = 0; j < temp.length; j++) {
char old = temp[j];
for (int i = -1; i <= 1; i++) {
int digit = old - '0';
if ((digit == 9 && i == 1) || (digit == 0 && i == -1)) {
continue;
}
temp[j] = (char) (i + digit + '0');
int newnum = Integer.parseInt(new String(temp));
if (!sieve[newnum] && !visited[newnum]) {
visited[newnum] = true;
pq.add(new int[] {cost + newnum, newnum});
}
}
temp[j] = old;
}
}
return -1;
}
}