Digit Operations to Make Two Integers Equal

Digit Operations to Make Two Integers Equal - Problem

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.

Important constraint: 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.

Input & Output

Example 1 — Basic Transformation

$ Input: n = 10, m = 12

› Output: 42

💡 Note: Path: 10 → 20 → 12. Cost = 10 + 20 + 12 = 42. We avoid 11 because it's prime.

Example 2 — Same Number

$ Input: n = 34, m = 34

› Output: 34

💡 Note: Numbers are already equal, so the cost is just the starting number 34.

Example 3 — Impossible Case

$ Input: n = 23, m = 56

› Output: -1

💡 Note: Starting number 23 is prime, so no transformations are allowed. Return -1.

Constraints

1 ≤ n, m ≤ 10⁴
n and m have the same number of digits
n and m are positive integers

Visualization

Tap to expand

Understanding the Visualization

Input

Two numbers n=10 and m=12 with same digit count

Transform

Change digits by ±1, avoid primes like 11

Output

Minimum cost path: 10→20→12 = 42

Key Takeaway

🎯 Key Insight: Model as shortest path problem where prime numbers are forbidden nodes

Asked in

G Google 15 f Meta 12 a Amazon 8

This is a shortest path problem where we need to transform one number to another through digit operations while avoiding prime numbers. The key insight is to model this as a graph where each non-prime number is a node, and use Dijkstra's algorithm to find the minimum cost path. Best approach is Dijkstra with priority queue. Time: O(10^d × log(10^d) × √n), Space: O(10^d).

Common Approaches

Approach	Time	Space	Notes
✓ BFS with All Paths	O(10^d × d)	O(10^d)	Explore all possible digit transformations using breadth-first search
Dijkstra's Algorithm	O(10^d × log(10^d) × √n)	O(10^d)	Use Dijkstra's shortest path algorithm with priority queue for optimal solution

BFS with All Paths — Algorithm Steps

Check if starting number is prime (return -1 if so)
Use BFS to explore all digit modifications
For each number, try +1/-1 on each digit
Skip if result is prime or out of bounds
Return minimum cost when target is reached

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin with n=10, target m=12

Explore

Try all digit +1/-1 operations

Filter

Skip prime numbers like 11

Result

Find shortest path: 10→20→12

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>

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

struct QueueNode {
    int num;
    int cost;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

void enqueue(struct Queue* q, int num, int cost) {
    struct QueueNode* node = malloc(sizeof(struct QueueNode));
    node->num = num;
    node->cost = cost;
    node->next = NULL;
    
    if (q->rear) {
        q->rear->next = node;
    } else {
        q->front = node;
    }
    q->rear = node;
}

bool dequeue(struct Queue* q, int* num, int* cost) {
    if (!q->front) return false;
    
    struct QueueNode* node = q->front;
    *num = node->num;
    *cost = node->cost;
    
    q->front = node->next;
    if (!q->front) q->rear = NULL;
    
    free(node);
    return true;
}

int solution(int n, int m) {
    if (n == m) return n;
    if (isPrime(n)) return -1;
    
    struct Queue q = {NULL, NULL};
    bool visited[100000] = {false};
    
    enqueue(&q, n, n);
    visited[n] = true;
    
    char nStr[10];
    sprintf(nStr, "%d", n);
    int numDigits = strlen(nStr);
    
    int currNum, cost;
    while (dequeue(&q, &currNum, &cost)) {
        char currStr[10];
        sprintf(currStr, "%0*d", numDigits, currNum);
        
        for (int i = 0; i < numDigits; i++) {
            int digit = currStr[i] - '0';
            
            // Try increasing digit
            if (digit < 9) {
                char newStr[10];
                strcpy(newStr, currStr);
                newStr[i] = (digit + 1) + '0';
                int newNum = atoi(newStr);
                
                if (newNum == m) return cost + newNum;
                
                if (newNum < 100000 && !visited[newNum] && !isPrime(newNum)) {
                    visited[newNum] = true;
                    enqueue(&q, newNum, cost + newNum);
                }
            }
            
            // Try decreasing digit
            if (digit > 0) {
                char newStr[10];
                strcpy(newStr, currStr);
                newStr[i] = (digit - 1) + '0';
                int newNum = atoi(newStr);
                
                if (newNum == m) return cost + newNum;
                
                if (newNum < 100000 && !visited[newNum] && !isPrime(newNum)) {
                    visited[newNum] = true;
                    enqueue(&q, newNum, cost + newNum);
                }
            }
        }
    }
    
    return -1;
}

int main() {
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);
    printf("%d\n", solution(n, m));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(10^d × d)

10^d possible numbers with d digits, each requiring prime check of O(√n)

✓ Linear Growth

Space Complexity

O(10^d)

Queue and visited set can store up to 10^d numbers

✓ Linear Space

8.8K Views

Medium Frequency

~35 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

BFS with All Paths — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler