Digit Operations to Make Two Integers Equal - Solution & Explanation

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.