Is Digit Operations to Make Two Integers Equal easy or hard?

The problem is rated Medium on LeetCode but requires recognizing a weighted graph hidden inside digit transformations. Candidates comfortable with Dijkstra’s algorithm, prime sieves, and state generation will find it manageable.

Digit Operations to Make Two Integers Equal Python/Java solution

The typical implementation uses Dijkstra’s algorithm with a priority queue. Generate digit neighbors, skip primes using a precomputed sieve, and update the minimum cost distance for each number. The same logic translates directly across Python (heapq), Java (PriorityQueue), and C++ (priority_queue).

How to solve Digit Operations to Make Two Integers Equal in O(N log N)?

Model the problem as a weighted graph and run Dijkstra’s algorithm. Precompute primes using a sieve, then generate neighbors by increasing or decreasing each digit. Use a min‑heap to track the lowest accumulated cost and stop once the target number is reached.

What is the best approach for Digit Operations to Make Two Integers Equal?

The most efficient approach is Dijkstra's shortest path algorithm. Each integer represents a node and digit +/- operations create edges with weights equal to the resulting number. A priority queue always processes the lowest cost state first, ensuring the minimum total cost path while skipping prime numbers.

Is Digit Operations to Make Two Integers Equal asked at Google/Amazon/Meta?

Problems combining graph traversal, shortest path algorithms, and number constraints frequently appear in interviews at companies like Google and Amazon. This problem specifically tests recognition of implicit graphs and applying Dijkstra’s algorithm correctly.

What data structure is used in Digit Operations to Make Two Integers Equal?

The key data structure is a min‑heap (priority queue) used in Dijkstra’s algorithm. Additional structures include a hash map or array for tracking minimum distances and a sieve array for fast prime detection.

What is the time complexity of Digit Operations to Make Two Integers Equal?

Using Dijkstra’s algorithm, the time complexity is roughly O(N log N * d), where N is the number of valid numbers in the search space and d is the number of digits. Each state generates up to 2*d neighbors and heap operations add the log N factor.

Description Hints 2 Solution Video 23:13

3377. Digit Operations to Make Two Integers Equal

Medium31.3% acceptance2 companies

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.

Example 1:

Input: n = 10, m = 12

Output: 85

Explanation:

We perform the following operations:

Increase the first digit, now n = 20.
Increase the second digit, now n = 21.
Increase the second digit, now n = 22.
Decrease the first digit, now n = 12.

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 < 10⁴
n and m consist of the same number of digits.

Asked at 2 companies

Microsoft

Google

Topics

Graph Heap (Priority Queue)Math Number Theory Shortest Path

Hints open one at a time

Hint 1

Consider a directed, weighted graph where an edge exists from a node x to a node y if and only if x can be transformed into y through a single operation.

Hint 2

Apply a shortest path algorithm on this graph to find the shortest path from n to m.

23:13

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minOperations(self, n: int, m: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

10
12

Input

4
8

Input

6
2

Your code is saved on this device.Solution