LeetCode 3377 - Digit Operations to Make Two Integers Equal

LeetCode Problem 3377

Difficulty: 🟡 Medium
Topics: Math, Graph Theory, Heap (Priority Queue), Number Theory, Shortest Path

Solution

Problem Understanding

The problem asks us to transform one integer n into another integer m by repeatedly modifying individual digits of n. At each step, we can increase a digit that is not 9 or decrease a digit that is not 0. However, there is a strict constraint: n cannot ever be a prime number during the transformation, including its initial value and the intermediate numbers.

The input consists of two integers n and m, guaranteed to have the same number of digits and bounded by $1 \le n, m < 10^4$, meaning we are dealing with numbers up to 4 digits. The output is the minimum total cost, where the cost is defined as the sum of all numbers that n takes during the transformations. If it is impossible to reach m without violating the non-prime constraint, we return -1.

Important edge cases include:

1. n or m themselves being prime-transformation is impossible.
2. Numbers where all digits are already at 0 or 9, limiting valid operations.
3. Multiple paths to reach m, but some paths may encounter prime numbers, so we cannot just greedily increment digits.

The key challenge is the non-prime constraint, which requires careful tracking of all intermediate numbers.

Approaches

The brute-force approach would attempt all sequences of digit modifications, checking every intermediate number for primality. This guarantees correctness but is exponential in the number of digits because each digit can change in multiple ways, and numbers can revert to previous states. For four-digit numbers, this approach is computationally infeasible.

The optimal approach recognizes this as a shortest path problem in a graph, where each valid integer (non-prime) is a node, and an edge exists between numbers that differ by a single allowed digit operation. Each edge weight is the new number's value, representing the cost. Using Dijkstra's algorithm, we can efficiently find the minimum total cost path from n to m, treating the sum of the integers along the path as the path cost.

Here, V is the number of non-prime integers with the same number of digits (up to 9000 for 4-digit numbers) and E is the number of edges (digit modifications).

Algorithm Walkthrough

1. Generate Non-Prime Numbers: Precompute all non-prime numbers with the same number of digits as n. This allows quick validation of candidate transformations.
2. Graph Representation: Treat each non-prime number as a node. An edge exists from number x to y if y can be obtained by increasing or decreasing a single digit of x according to the rules.
3. Dijkstra Initialization: Initialize a min-heap (priority queue) with the starting number n and its cost equal to n. Maintain a dictionary to track the minimum cost to reach each number.
4. Exploration: Pop the smallest-cost number from the heap. For each valid digit change, generate a neighbor number. If the neighbor is non-prime and the total cost to reach it is lower than previously recorded, update the cost and push it onto the heap.
5. Termination: Stop when m is popped from the heap, since Dijkstra guarantees this is the minimum cost path. If the heap is exhausted without reaching m, return -1.

Why it works: Dijkstra's algorithm ensures that when a node is first visited, the recorded cost is minimal. By limiting edges to non-prime numbers only, we satisfy the problem's constraint and compute the minimal sum along a valid transformation path.

Python Solution

import heapq

class Solution:
    def minOperations(self, n: int, m: int) -> int:
        if self.is_prime(n) or self.is_prime(m):
            return -1
        
        digits = len(str(n))
        lower, upper = 10**(digits-1), 10**digits - 1
        
        # Precompute non-prime numbers
        non_primes = set(i for i in range(lower, upper+1) if not self.is_prime(i))
        
        heap = [(n, n)]  # (total_cost, current_number)
        min_cost = {n: n}
        
        while heap:
            cost, num = heapq.heappop(heap)
            if num == m:
                return cost
            
            s = str(num)
            for i, ch in enumerate(s):
                for d in [-1, 1]:
                    new_digit = int(ch) + d
                    if 0 <= new_digit <= 9:
                        new_num = int(s[:i] + str(new_digit) + s[i+1:])
                        if new_num in non_primes:
                            new_cost = cost + new_num
                            if new_num not in min_cost or new_cost < min_cost[new_num]:
                                min_cost[new_num] = new_cost
                                heapq.heappush(heap, (new_cost, new_num))
        return -1
    
    def is_prime(self, x: int) -> bool:
        if x < 2:
            return False
        for i in range(2, int(x**0.5)+1):
            if x % i == 0:
                return False
        return True

The Python code follows the algorithm closely. It precomputes non-prime numbers, initializes Dijkstra's heap with the starting number, and explores all valid digit modifications. The is_prime helper checks for primality. We track minimum costs in a dictionary and terminate immediately upon reaching m.

Go Solution

package main

import (
    "container/heap"
    "math"
)

type Item struct {
    num, cost int
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func minOperations(n int, m int) int {
    if isPrime(n) || isPrime(m) {
        return -1
    }
    
    digits := int(math.Log10(float64(n))) + 1
    lower, upper := int(math.Pow10(digits-1)), int(math.Pow10(digits)) - 1
    
    nonPrimes := make(map[int]bool)
    for i := lower; i <= upper; i++ {
        if !isPrime(i) {
            nonPrimes[i] = true
        }
    }
    
    pq := &PriorityQueue{}
    heap.Init(pq)
    heap.Push(pq, Item{num: n, cost: n})
    
    minCost := make(map[int]int)
    minCost[n] = n
    
    for pq.Len() > 0 {
        item := heap.Pop(pq).(Item)
        num, cost := item.num, item.cost
        if num == m {
            return cost
        }
        
        s := []byte(fmt.Sprintf("%d", num))
        for i := 0; i < len(s); i++ {
            for _, d := range []int{-1, 1} {
                newDigit := int(s[i]-'0') + d
                if newDigit >= 0 && newDigit <= 9 {
                    s[i] = byte(newDigit + '0')
                    newNum := 0
                    for _, ch := range s {
                        newNum = newNum*10 + int(ch-'0')
                    }
                    if nonPrimes[newNum] {
                        newCost := cost + newNum
                        if c, ok := minCost[newNum]; !ok || newCost < c {
                            minCost[newNum] = newCost
                            heap.Push(pq, Item{num: newNum, cost: newCost})
                        }
                    }
                    s[i] = byte(int(s[i]-'0') - d + '0') // revert
                }
            }
        }
    }
    
    return -1
}

func isPrime(x int) bool {
    if x < 2 { return false }
    for i := 2; i*i <= x; i++ {
        if x % i == 0 { return false }
    }
    return true
}

In Go, we implement a min-heap using container/heap. The key difference is managing the heap and converting digits using byte slices. Reverting digits after exploration is necessary to avoid side effects.

Worked Examples

Example 1: n = 10, m = 12