#3377

Digit Operations to Make Two Integers Equal

medium · 29.9% accepted · 132 likes · top 7%

math · graph theory · heap (priority queue) · number theory · shortest path

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.

Solution