Maximum Difference by Remapping a Digit

Easy

Asked by:

62 views

Topics:

StringsGreedy Algorithms

You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.

Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.

Notes:

When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of d1 in num with d2.
Bob can remap a digit to itself, in which case num does not change.
Bob can remap different digits for obtaining minimum and maximum values respectively.
The resulting number after remapping can contain leading zeroes.

Example 1:

Input: num = 11891
Output: 99009
Explanation: 
To achieve the maximum value, Bob can remap the digit 1 to the digit 9 to yield 99899.
To achieve the minimum value, Bob can remap the digit 1 to the digit 0, yielding 890.
The difference between these two numbers is 99009.

Example 2:

Input: num = 90
Output: 99
Explanation:
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
Thus, we return 99.

Constraints:

1 <= num <= 10⁸

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 is the range of possible values for the input integer?
Can the input number be negative or zero?
If multiple digits can be remapped to maximize/minimize the difference, which one should I choose?
If remapping all digits results in the same maximum difference, what should I return?
Can I assume the input is always a valid integer or should I handle potential parsing errors?

Brute Force Solution

Approach

We want to find the biggest and smallest numbers we can make by replacing one digit in the original number with another. The brute force way is to try *every* possible replacement and see what happens.

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

Consider each digit (0 through 9) as a possible replacement for a digit in the original number.
For each possible replacement digit, also consider each digit in the original number (0 through 9) as the digit to be replaced.
For each combination of replacement and replaced digits, create a new number by going through the original number and substituting every occurrence of the 'replaced' digit with the 'replacement' digit.
Once you've done that, you'll have one possible version of the remapped number. Convert this into a number if it isn't already.
Repeat the above steps for every combination of replacement and replaced digits, noting down each new number you get.
Once you've checked all possible replacements to create the largest and smallest values, compare all the numbers you created and identify the largest and smallest.
Finally, subtract the smallest number from the largest number to find the maximum difference.

Code Implementation

def max_difference_by_remapping_a_digit(number):
    number_string = str(number)
    remapped_numbers = []

    # Iterate through all possible replacement digits
    for replacement_digit in range(10):
        # Iterate through all possible digits to be replaced
        for digit_to_replace in range(10):
            new_number_string = ""

            # Create the remapped number
            for digit_char in number_string:
                if int(digit_char) == digit_to_replace:
                    new_number_string += str(replacement_digit)
                else:
                    new_number_string += digit_char

            # Prevent leading zeros and append to the list
            if len(new_number_string) > 1 and new_number_string[0] == '0':
                continue

            remapped_numbers.append(int(new_number_string))

    # Handle the case when no valid remapped numbers exist
    if not remapped_numbers:
        return 0

    # Find max and min remapped numbers
    max_number = max(remapped_numbers)

    min_number = min(remapped_numbers)

    # The maximum difference is the difference between max and min
    maximum_difference = max_number - min_number

    return maximum_difference

Big(O) Analysis

Time Complexity

O(n) – Let n be the number of digits in the input number. The algorithm iterates through all possible replacement digits (0-9, a constant 10) and for each possible replacement digit, iterates through all possible digits to be replaced (0-9, another constant 10). Inside the inner loop, it iterates through the digits of the number 'n' times to perform the replacement. Hence, for each digit, it creates a new number and finds the max and min out of the new numbers. So, we have two constant loops and one loop that depends on the number of digits 'n'. The complexity is therefore O(n).

Space Complexity

O(1) – The algorithm generates new numbers by replacing digits in the original number. However, it only needs to store the current largest and smallest numbers found so far. No data structures whose size depends on the input number's length are required, making the space used constant. The space usage does not scale with the size of the input number N, where N is the number of digits in the input. Therefore, the space complexity is O(1).

Optimal Solution

Approach

To find the maximum difference, we aim to create the largest and smallest possible numbers by remapping a single digit. The key is to choose the digit and the remapping value intelligently for both maximum and minimum values.

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

To find the largest number, scan the original number from left to right.
Find the first digit that is not a '9'.
Replace all occurrences of this digit with '9' to create the largest possible number.
To find the smallest number, consider the first digit.
If the first digit is '1', look for the next digit that is not '0' or '1'. If the first digit isn't '1', replace it to '1'.
If the first digit is not '1', replace all occurrences of the first digit with '1'.
If the first digit is '1', replace all occurrences of the next non-zero/non-one digit with '0'.
Subtract the smallest number from the largest number to obtain the maximum difference.

Code Implementation

def max_difference_by_remapping_digit(number):
    number_string = str(number)

    # Construct the largest possible number
    largest_number_string = list(number_string)
    digit_to_replace_max = None
    for digit in largest_number_string:
        if digit != '9':
            digit_to_replace_max = digit
            break

    if digit_to_replace_max is not None:
        for i in range(len(largest_number_string)):
            if largest_number_string[i] == digit_to_replace_max:
                largest_number_string[i] = '9'
        largest_number = int("".join(largest_number_string))
    else:
        largest_number = number

    # Construct the smallest possible number
    smallest_number_string = list(number_string)
    digit_to_replace_min = None

    # Need to handle the first digit carefully
    if smallest_number_string[0] != '1':
        digit_to_replace_min = smallest_number_string[0]
        replacement_digit = '1'
    else:
        replacement_digit = '0'
        for i in range(1, len(smallest_number_string)):
            if smallest_number_string[i] != '0' and smallest_number_string[i] != '1':
                digit_to_replace_min = smallest_number_string[i]
                break

    if digit_to_replace_min is not None:
        for i in range(len(smallest_number_string)):
            if smallest_number_string[i] == digit_to_replace_min:
                smallest_number_string[i] = replacement_digit
        smallest_number = int("".join(smallest_number_string))
    else:
        smallest_number = number

    # Calculate the maximum difference
    max_difference = largest_number - smallest_number
    return max_difference

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the digits of the input number (n digits) a constant number of times (maximum of two passes) to find the digit to remap for creating the largest and smallest numbers. The replacement process also iterates through the digits once for each replacement. Therefore, the dominant operation is iterating through the digits a few times, resulting in a time complexity proportional to the number of digits, which is O(n).

Space Complexity

O(1) – The algorithm primarily manipulates the input string in place or creates string representations of numbers. While the algorithm creates largest and smallest numbers, these numbers have the same number of digits as the input number. Therefore, the auxiliary space is dominated by a few variables to store digits or boolean flags, and the creation of two new strings of the same length as the input. However, the length of the number's string representation is dependent on the number of digits in the number itself, which is logarithmic to the number's value. Since the maximum possible digits for an integer is fixed for a given system (e.g. 32-bit or 64-bit integer), the auxiliary space can be considered constant, leading to an O(1) space complexity.

Edge Cases

Case	How to Handle
Input number is 0	Remapping to 9 gives the maximum possible number, and remapping to 0 gives the minimum possible number.
Input number consists of all the same digits (e.g., 11111)	Remapping all digits to 9 for max and all digits to 0 (if not leading digit) or 1 (if leading digit) for min must be handled carefully.
Large input number that could cause integer overflow when remapping	Use long type for intermediate calculations or string manipulation to avoid overflow.
Leading digit is remapped to 0 for minimum, resulting in invalid number representation	If the leading digit is remapped to 0, find the smallest non-zero digit and remap that to 0 instead.
The largest digit is already 9, so no remapping can increase its value	In such cases, find the next largest and remap that.
The smallest digit is already 0, so no remapping can decrease its value	In such cases, find the next smallest and remap that.
Input number is a single digit number	Remap the digit to 9 for max and to 0 for min.
No digit replacement results in a change to the input number	For example the largest possible is already the number, so the subtraction will result in 0.

Input number is 0

How to Handle:

Remapping to 9 gives the maximum possible number, and remapping to 0 gives the minimum possible number.

Input number consists of all the same digits (e.g., 11111)

How to Handle:

Remapping all digits to 9 for max and all digits to 0 (if not leading digit) or 1 (if leading digit) for min must be handled carefully.

Large input number that could cause integer overflow when remapping

How to Handle:

Use long type for intermediate calculations or string manipulation to avoid overflow.

Leading digit is remapped to 0 for minimum, resulting in invalid number representation

How to Handle:

If the leading digit is remapped to 0, find the smallest non-zero digit and remap that to 0 instead.

The largest digit is already 9, so no remapping can increase its value

How to Handle:

In such cases, find the next largest and remap that.

The smallest digit is already 0, so no remapping can decrease its value

How to Handle:

In such cases, find the next smallest and remap that.

Input number is a single digit number

How to Handle:

Remap the digit to 9 for max and to 0 for min.

No digit replacement results in a change to the input number

How to Handle:

For example the largest possible is already the number, so the subtraction will result in 0.