We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Digit Operations to Make Two Integers Equal

Difficulty: Medium

Problem Description

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.

Key Insights

  • Both integers have the same number of digits, which simplifies the comparison.
  • The operations on n are limited by the requirement that n cannot be prime at any point.
  • Each transformation incurs a cost, and we need to minimize this cost while reaching m.
  • A breadth-first search (BFS) can be used to explore all valid transformations of n until we reach m or exhaust possibilities.
  • A primality check is required to ensure n is not prime after any operation.

Space and Time Complexity

Time Complexity: O(10^d * d), where d is the number of digits (up to 4 in this case). Space Complexity: O(10^d) for storing the states in the BFS.

Solution

To solve the problem, we can use a breadth-first search (BFS) approach. The key steps include:

  1. Initialize a queue to explore different states of n and a set to track visited states.
  2. At each state, generate all possible transformations by increasing or decreasing each digit of n that is not 9 or 0, respectively.
  3. For each new state, check if it matches m. If it does, calculate the total cost of transformations and return it.
  4. Ensure that n is not prime after any transformation. If a prime is encountered, that transformation is discarded.
  5. If the queue is exhausted without reaching m, return -1.

Code Solutions

from collections import deque

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def min_cost_to_transform(n, m):
    n_str = str(n)
    m_str = str(m)
    if len(n_str) != len(m_str):
        return -1

    queue = deque([(n, 0)])  # (current_value, current_cost)
    visited = set()
    visited.add(n)
    
    min_cost = float('inf')
    
    while queue:
        current, cost = queue.popleft()
        
        if current == m:
            min_cost = min(min_cost, cost)
            continue
        
        current_str = str(current)
        
        for i in range(len(current_str)):
            digit = int(current_str[i])
            
            # Increase digit
            if digit < 9:
                new_digit = digit + 1
                new_number = current_str[:i] + str(new_digit) + current_str[i+1:]
                new_number = int(new_number)
                if new_number not in visited and not is_prime(new_number):
                    visited.add(new_number)
                    queue.append((new_number, cost + new_number))
            
            # Decrease digit
            if digit > 0:
                new_digit = digit - 1
                new_number = current_str[:i] + str(new_digit) + current_str[i+1:]
                new_number = int(new_number)
                if new_number not in visited and not is_prime(new_number):
                    visited.add(new_number)
                    queue.append((new_number, cost + new_number))
    
    return min_cost if min_cost != float('inf') else -1
← Back to All Questions