Maximum Difference by Remapping a Digit

Difficulty: Easy | Acceptance: 75.80% | Paid: No Topics: Math, Greedy

You are given an integer num. You are allowed to remap exactly one digit in num to any other digit to create num1. You are allowed to remap exactly one digit in num to any other digit to create num2. Return the maximum difference between num1 and num2.

• Examples
• Constraints
• Brute Force Simulation
• Greedy String Manipulation

Examples

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^8

Brute Force Simulation

Intuition We can simulate the process of remapping every digit to every other possible digit. Since the number of digits is at most 9 (as num <= 10^8), and there are only 10 possible digits (0-9) to remap to, the total number of combinations is small. We can generate all possible num1 and num2 values and find the maximum difference.

Steps

• Convert the number to a string to easily access digits.
• Iterate through each digit position.
• For each position, iterate through all possible target digits (0-9).
• If the target digit is different from the original digit, create a new number by replacing all occurrences of the original digit with the target digit.
• Keep track of the maximum value found (num1) and the minimum value found (num2).
• Return num1 - num2.

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        max_val = -1
        min_val = float('inf')
        
        # Iterate through each unique digit in the number to act as the source
        # Actually, we should iterate through each position to determine the source digit
        # But since we remap ALL occurrences of a digit, we just need to try remapping each unique digit present.
        unique_digits = set(s)
        
        for source_d in unique_digits:
            for target_d in '0123456789':
                if source_d == target_d:
                    continue
                
                # Remap all occurrences of source_d to target_d
                new_s = s.replace(source_d, target_d)
                val = int(new_s)
                
                max_val = max(max_val, val)
                min_val = min(min_val, val)
                
        return max_val - min_val

Complexity

• Time: O(N * 10) where N is the number of digits. Since N is small, this is effectively O(1).
• Space: O(N) to store the string representation.
• Notes: Simple to implement and understand, but iterates through all possibilities.

Greedy String Manipulation

Intuition To maximize the number, we want the most significant digits to be as large as possible (9). To minimize the number, we want the most significant digits to be as small as possible (0), with the constraint that we cannot have leading zeros (unless the number itself becomes 0).

Steps

• Convert the number to a character array or string.
• Maximize:
  • Find the first digit that is not 9.
  • Replace all occurrences of that digit with 9.
  • If all digits are 9, replace the last digit with 8 (since we must remap to a different digit).
• Minimize:
  • Find the first digit that is not 0.
  • If this digit is the first digit (most significant) and the number has more than one digit, we cannot remap it to 0 (as it would create leading zeros).
    • In this case, look for the next digit that is not 0.
    • If found, replace all occurrences of that digit with 0.
    • If not found (all digits are the same, e.g., 555), replace all occurrences of the first digit with 1.
  • If the first non-0 digit is not the most significant digit (or the number is a single digit), replace all occurrences of that digit with 0.
• Convert the resulting strings back to integers and return the difference.

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = list(str(num))
        
        # Calculate Max
        max_s = s.copy()
        target = None
        for c in max_s:
            if c != '9':
                target = c
                break
        if target:
            for i in range(len(max_s)):
                if max_s[i] == target:
                    max_s[i] = '9'
        else:
            # All 9s, change last to 8
            max_s[-1] = '8'
            
        # Calculate Min
        min_s = s.copy()
        target = None
        # Find first non-0
        for i, c in enumerate(min_s):
            if c != '0':
                target = c
                target_idx = i
                break
        
        if target:
            if target_idx == 0 and len(min_s) > 1:
                # Cannot remap first digit to 0
                # Find next non-0
                next_target = None
                for i in range(1, len(min_s)):
                    if min_s[i] != '0':
                        next_target = min_s[i]
                        break
                if next_target:
                    for i in range(len(min_s)):
                        if min_s[i] == next_target:
                            min_s[i] = '0'
                else:
                    # All digits are same (e.g. 555), remap to 1
                    for i in range(len(min_s)):
                        if min_s[i] == target:
                            min_s[i] = '1'
            else:
                # Safe to remap to 0
                for i in range(len(min_s)):
                    if min_s[i] == target:
                        min_s[i] = '0'
        else:
            # All 0s (num=0), remap to 1
            min_s[-1] = '1'
            
        return int(''.join(max_s)) - int(''.join(min_s))

Complexity

• Time: O(N) where N is the number of digits. We iterate through the string a constant number of times.
• Space: O(N) to store the character arrays.
• Notes: Optimal solution with linear time complexity.