LeetCode in Kotlin
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.PriorityQueue
class Solution {
fun minOperations(n: Int, m: Int): Int {
val limit = 100000
val sieve = BooleanArray(limit + 1)
val visited = BooleanArray(limit)
sieve.fill(true)
sieve[0] = false
sieve[1] = false
var i = 2
while (i * i <= limit) {
if (sieve[i]) {
var j = i * i
while (j <= limit) {
sieve[j] = false
j += i
}
}
i++
}
if (sieve[n]) {
return -1
}
val pq = PriorityQueue<IntArray>(Comparator { a: IntArray, b: IntArray -> a[0] - b[0] })
visited[n] = true
pq.add(intArrayOf(n, n))
while (pq.isNotEmpty()) {
val current = pq.poll()
val cost = current[0]
val num = current[1]
val temp = num.toString().toCharArray()
if (num == m) {
return cost
}
for (j in temp.indices) {
val old = temp[j]
for (i in -1..1) {
val digit = old.code - '0'.code
if ((digit == 9 && i == 1) || (digit == 0 && i == -1)) {
continue
}
temp[j] = (i + digit + '0'.code).toChar()
val newNum = String(temp).toInt()
if (!sieve[newNum] && !visited[newNum]) {
visited[newNum] = true
pq.add(intArrayOf(cost + newNum, newNum))
}
}
temp[j] = old
}
}
return -1
}
}