Digit Operations to Make Two Integers Equal

Medium

Asked by:

4 views

Topics:

GraphsDynamic Programming

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.

Example 1:

Input: n = 10, m = 12

Output: 85

Explanation:

We perform the following operations:

Increase the first digit, now n = 20.
Increase the second digit, now n = 21.
Increase the second digit, now n = 22.
Decrease the first digit, now n = 12.

Example 2:

Input: n = 4, m = 8

Output: -1

Explanation:

It is impossible to make n equal to m.

Example 3:

Input: n = 6, m = 2

Output: -1

Explanation:

Since 2 is already a prime, we can't make n equal to m.

Constraints:

1 <= n, m < 10⁴
n and m consist of the same number of digits.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the integer inputs num1 and num2?
Are num1 and num2 guaranteed to have the same number of digits?
What should I return if num1 and num2 are equal?
What should I return if either num1 or num2 is null or otherwise invalid?
Are num1 and num2 always non-negative integers?

Brute Force Solution

Approach

The goal is to find the fewest digit changes needed to make two numbers equal. The brute force approach considers every possible combination of digit changes to both numbers until a match is found.

Here's how the algorithm would work step-by-step:

Start by trying to change zero digits in the first number and zero digits in the second number to see if they are already equal.
Next, try changing one digit in the first number and keeping the second number unchanged, then try changing one digit in the second number and keeping the first number unchanged. Check if the numbers are now equal.
Then, try changing one digit in the first number and one digit in the second number. Check if the numbers are equal.
Continue increasing the number of digit changes you make, always checking if the numbers become equal after each set of changes.
Keep track of the number of changes needed in each attempt.
The process stops once the two numbers become equal, and the fewest number of changes needed is recorded.

Code Implementation

def digit_operations_brute_force(first_number, second_number):
    first_number_string = str(first_number)
    second_number_string = str(second_number)
    queue = [first_number_string]
    visited = {first_number_string}

    while queue:
        current_number_string = queue.pop(0)

        if current_number_string == second_number_string:
            return True

        # Explore possible digit changes.
        for digit_index in range(len(current_number_string)):
            current_digit = int(current_number_string[digit_index])

            # Subtract 1 from the digit.
            new_digit_subtract = current_digit - 1

            new_number_string_subtract = list(current_number_string)

            new_number_string_subtract[digit_index] = str(new_digit_subtract)
            new_number_string_subtract = "".join(new_number_string_subtract)

            if 0 <= new_digit_subtract <= 9 and new_number_string_subtract not in visited:

                #Only add valid changes to the queue.
                queue.append(new_number_string_subtract)
                visited.add(new_number_string_subtract)

            # Add 1 to the digit.
            new_digit_add = current_digit + 1
            new_number_string_add = list(current_number_string)
            new_number_string_add[digit_index] = str(new_digit_add)
            new_number_string_add = "".join(new_number_string_add)

            if 0 <= new_digit_add <= 9 and new_number_string_add not in visited:

                #Avoid infinite loops by tracking visited states.
                queue.append(new_number_string_add)
                visited.add(new_number_string_add)

    return False

Big(O) Analysis

Time Complexity

O(10^(2n)) – Let n be the number of digits in each integer. The algorithm explores all possible combinations of digit changes in both numbers, increasing the number of changes incrementally. In the worst case, it could potentially change every digit in both numbers. Changing a single digit can be any of the 10 digits (0-9), so changing 'k' digits leads to 10^k combinations. Since we are considering combinations of changes in BOTH numbers, and each number can have at most 'n' digits changed, the total number of combinations explored can grow up to approximately 10^n * 10^n = 10^(2n). Therefore, the time complexity is O(10^(2n)).

Space Complexity

O(1) – The provided brute force approach primarily involves iterative digit changing and comparison. The plain English explanation does not suggest the use of any auxiliary data structures such as lists, hash maps, or recursion. Therefore, the space complexity is determined by the storage of a few integer variables like the number of changes made so far, which remains constant regardless of the size of the input numbers. Thus, the auxiliary space used is O(1).

Optimal Solution

Approach

The problem asks us to transform one number into another using digit operations. The key idea is to work digit by digit, figuring out what operation (add or subtract) transforms the corresponding digits, and accumulating the total cost.

Here's how the algorithm would work step-by-step:

First, look at the two numbers and line them up so you can compare each digit in the same place (ones place, tens place, etc.).
Start from the rightmost digit (the ones place). See how different the digits are. This tells you how much you need to add or subtract.
Keep track of this difference. This represents the cost of transforming that specific digit.
Move to the next digit to the left (the tens place). Repeat the comparison and difference calculation. But here's the trick: you need to also take into account any 'carry-over' or 'borrow' from the previous digit.
Add or subtract that 'carry-over' from the current difference.
Keep repeating this process for all the digits, always accounting for any 'carry-over' or 'borrow' from the digit to the right.
At the very end, the total difference accumulated represents the minimum number of digit operations required.

Code Implementation

def min_digit_operations(number_one, number_two):
    number_one_string = str(number_one)
    number_two_string = str(number_two)
    length_one = len(number_one_string)
    length_two = len(number_two_string)

    if length_one != length_two:
        return -1

    effort = 0

    for digit_index in range(length_one):
        digit_one = int(number_one_string[digit_index])
        digit_two = int(number_two_string[digit_index])

        if digit_one != digit_two:
            # Count the absolute difference.
            effort += abs(digit_one - digit_two)

    return effort

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the two input numbers once, where n is the number of digits in the longer number. For each digit, it performs a constant amount of work: comparing the digits, calculating the difference, and handling any carry-over or borrow. Thus, the time complexity is directly proportional to the number of digits, resulting in O(n) time complexity.

Space Complexity

O(1) – The algorithm iteratively compares and updates differences between digits, along with a carry-over value. It does not create any auxiliary data structures that scale with the size of the input numbers. Only a constant amount of extra space is used to store the carry-over and intermediate difference values. Therefore, the space complexity is constant.

Edge Cases

Case	How to Handle
num1 and num2 are equal	Return 0 immediately as no operations are needed.
num1 or num2 is null or empty string	Throw IllegalArgumentException since the input should be valid integers.
num1 and num2 have different lengths (number of digits)	Throw IllegalArgumentException because they must have same number of digits for transformation to be possible.
Large integers potentially leading to integer overflow during calculation of digit differences	The absolute difference between digits will not cause an overflow as the maximum difference is 9.
num1 or num2 contains non-digit characters	Throw IllegalArgumentException since the input is expected to be valid numeric strings.
Leading zeros in either num1 or num2	The string representation handles leading zeros without causing issues during character by character comparison and difference calculation.
Very long numbers (e.g., hundreds of digits) impacting performance.	The solution scales linearly with the number of digits, so performance should still be acceptable.
num1 and num2 are identical except for a single digit at a specific index.	The solution will correctly calculate the absolute difference of these digits and return that as the number of operations.

num1 and num2 are equal

How to Handle:

Return 0 immediately as no operations are needed.

num1 or num2 is null or empty string

How to Handle:

Throw IllegalArgumentException since the input should be valid integers.

num1 and num2 have different lengths (number of digits)

How to Handle:

Throw IllegalArgumentException because they must have same number of digits for transformation to be possible.

Large integers potentially leading to integer overflow during calculation of digit differences

How to Handle:

The absolute difference between digits will not cause an overflow as the maximum difference is 9.

num1 or num2 contains non-digit characters

How to Handle:

Throw IllegalArgumentException since the input is expected to be valid numeric strings.

Leading zeros in either num1 or num2

How to Handle:

The string representation handles leading zeros without causing issues during character by character comparison and difference calculation.

Very long numbers (e.g., hundreds of digits) impacting performance.

How to Handle:

The solution scales linearly with the number of digits, so performance should still be acceptable.

num1 and num2 are identical except for a single digit at a specific index.

How to Handle:

The solution will correctly calculate the absolute difference of these digits and return that as the number of operations.