Skip to main content
Talentd

Digit Operations to Make Two Integers Equal - Solution & Explanation

MediumMathGraphHeap (Priority Queue)Number Theory6 min readAsked at: Microsoft, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given two integers n and m. In one operation, you can increase or decrease any single digit by 1. Every intermediate number must be non‑prime. Each move adds the value of the resulting number to the total cost. The task is to reach m from n with the minimum total cost.

Approach 1: Graph Traversal with BFS (Unweighted Assumption) (Time: O(V + E), Space: O(V))

A straightforward idea is to treat each valid number as a node in a graph. From any number, generate neighbors by incrementing or decrementing each digit. BFS can explore all reachable numbers while skipping primes using a number theory primality check. However, this approach assumes each operation has equal cost. In this problem the cost depends on the resulting number, so BFS does not guarantee the minimum total cost. It only works if all edge weights are identical, which is not the case here.

Approach 2: Dijkstra's Algorithm on Implicit Graph (Time: O(N log N * d), Space: O(N))

The correct model is a weighted shortest path problem. Treat every valid non‑prime integer as a node and each digit modification as an edge. The edge weight equals the numeric value of the resulting state. Use graph traversal with Dijkstra’s algorithm and a priority queue to always expand the state with the smallest accumulated cost.

First precompute primes using a sieve up to the maximum possible value. If the starting number n is prime, no path exists. During traversal, convert the number to a digit array, try +1 and -1 for each digit, rebuild the new number, and skip values that become prime or leave the valid digit range. Push valid neighbors into the min‑heap with updated cost. Maintain a distance map to avoid revisiting states with higher cost.

This approach efficiently explores the state space while guaranteeing the minimum total cost. The number of states is bounded by all numbers with the same digit length, and each state generates at most 2 * d neighbors where d is the digit count.

Recommended for interviews: Dijkstra’s shortest path approach. Interviewers expect you to recognize that digit transformations create a graph and the varying operation cost makes it a weighted shortest path problem. Mentioning the BFS idea first shows understanding of the graph structure, but switching to Dijkstra demonstrates algorithmic maturity.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph Traversal with BFSO(V + E)O(V)Useful for understanding the state graph when all operations have equal cost
Dijkstra Shortest Path with Priority QueueO(N log N * d)O(N)General solution when operations have different costs
A* Search OptimizationO(N log N)O(N)When a good heuristic (digit difference estimate) can guide the search

Video Solution

3377. Digit Operations to Make Two Integers Equal | Dijkstras | Prime Sieve | Graph + Math • Aryan Mittal • 2,202 views views

Watch 2 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Digit Operations to Make Two Integers Equal with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer