Digit operations to make two integers equal

Math Graph Theory Heap (Priority Queue) Number Theory Shortest Path

29.8% acceptance

Feb 24, 2026

132

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

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_operations(n: i32, m: i32) -> i32 {
    // If m is prime or n is prime, return -1
    // Use Dijkstra: state = current number, cost = sum of values visited
    // Transitions: change one digit by ±1 (result must be non-prime, same digit count)
    
    fn is_prime(x: i32) -> bool {
      if x < 2 { return false; }
      if x == 2 { return true; }
      if x % 2 == 0 { return false; }
      let mut i = 3;
      while i * i <= x {
        if x % i == 0 { return false; }
        i += 2;
      }
      true
    }
    
    fn digit_count(x: i32) -> u32 {
      if x == 0 { 1 } else { x.ilog10() + 1 }
    }
    
    if is_prime(n) || is_prime(m) {
      return -1;
    }
    
    let dc = digit_count(n);
    let limit = 10_i32.pow(dc);
    let lo = 10_i32.pow(dc - 1);
    
    // Dijkstra
    use std::collections::BinaryHeap;
    use std::cmp::Reverse;
    let mut dist = vec![i64::MAX; limit as usize];
    dist[n as usize] = n as i64;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((n as i64, n as i32)));
    
    while let Some(Reverse((cost, cur))) = heap.pop() {
      if cur == m {
        return cost as i32;
      }
      if cost > dist[cur as usize] {
        continue;
      }
      // Try changing each digit by ±1
      let digits: Vec<i32> = {
        let mut d = vec![];
        let mut tmp = cur;
        while tmp > 0 {
          d.push(tmp % 10);
          tmp /= 10;
        }
        d.reverse();
        d
      };
      let nd = digits.len();
      for pos in 0..nd {
        for delta in [-1i32, 1] {
          let new_digit = digits[pos] + delta;
          if new_digit < 0 || new_digit > 9 { continue; }
          // Reconstruct number
          let mut next = 0i32;
          for (j, &d) in digits.iter().enumerate() {
            let dj = if j == pos { new_digit } else { d };
            next = next * 10 + dj;
          }
          if next < lo || next >= limit { continue; }
          if is_prime(next) { continue; }
          let new_cost = cost + next as i64;
          if new_cost < dist[next as usize] {
            dist[next as usize] = new_cost;
            heap.push(Reverse((new_cost, next)));
          }
        }
      }
    }
    
    -1
  }
}