Problem Description

You are given an integer num. Bob can choose any digit (0-9) that appears in num and replace all occurrences of that digit with any other digit (0-9). This remapping operation changes the original number.

Your task is to find the difference between the maximum possible value and minimum possible value that Bob can create by performing exactly one remapping operation.

Key points to understand:

• Bob must remap exactly one digit to another digit (can be the same digit)
• When a digit is remapped, ALL occurrences of that digit in the number are replaced
• Different digits can be chosen for creating the maximum and minimum values
• Leading zeros are allowed in the resulting number

For example, with num = 11891:

• To maximize: Bob can remap digit 1 to 9, getting 99899
• To minimize: Bob can remap digit 1 to 0, getting 00890 (which equals 890)
• The difference is 99899 - 890 = 99009

Another example with num = 90:

• To maximize: Bob can remap digit 0 to 9, getting 99
• To minimize: Bob can remap digit 9 to 0, getting 00 (which equals 0)
• The difference is 99 - 0 = 99

The solution requires finding the optimal remapping strategies for both maximum and minimum values, then returning their difference.

Intuition

To maximize the difference, we need to make the number as large as possible in one case and as small as possible in another case.

For minimizing the value, we want to replace some digit with 0 to reduce the number as much as possible. Which digit should we choose? The most significant (leftmost) digit has the greatest impact on the number's value. So we should replace the first digit s[0] with 0. This ensures we're reducing the number by the maximum amount possible - turning all occurrences of that first digit into zeros.

For maximizing the value, we want to replace some digit with 9 to increase the number as much as possible. But which digit should we choose? We need to find the first digit from left to right that isn't already 9. Why? Because:

• Digits on the left have more weight (contribute more to the number's value)
• If a digit is already 9, replacing it with 9 doesn't change anything
• We want to find the leftmost non-9 digit and change all its occurrences to 9

The greedy strategy works here because:

1. For minimum: The first digit appears at the most significant position, so replacing it with 0 gives us the smallest possible result
2. For maximum: The first non-9 digit from the left is the one that, when changed to 9, will give us the largest increase in value

For example, in 11891:

• First digit is 1, so minimum = 00890 = 890 (replace all 1s with 0)
• First non-9 digit is 1, so maximum = 99899 (replace all 1s with 9)
• Difference = 99899 - 890 = 99009

Learn more about Greedy and Math patterns.

Solution Approach

The implementation follows the greedy strategy we identified:

1. Convert number to string: First, convert the integer num to a string s to easily access and manipulate individual digits.

2. Find the minimum value:

   • Take the first character s[0] of the string
   • Replace all occurrences of s[0] with '0' using the replace() method
   • Convert the result back to an integer to get the minimum value mi
   • Example: For s = "11891", s[0] = '1', so mi = int("00890") = 890

3. Find the maximum value:

   • Iterate through each character c in the string s
   • Find the first character that is not '9'
   • Once found, replace all occurrences of this character with '9'
   • Convert the result back to an integer to get the maximum value
   • Example: For s = "11891", the first non-'9' character is '1', so maximum = int("99899") = 99899

4. Calculate the difference:

   • Return maximum - mi
   • If all digits are '9' (the loop completes without finding a non-'9' digit), the maximum value is the original number itself, so return num - mi

The algorithm runs in O(n) time where n is the number of digits, as we traverse the string at most twice (once for minimum, once for maximum). The space complexity is O(n) for storing the string representation of the number.

The key insight is that Python's str.replace(old, new) method replaces ALL occurrences of the old character with the new character, which perfectly matches our requirement of remapping all instances of a chosen digit.

Example Walkthrough

Let's walk through the solution with num = 2736:

Step 1: Convert to string

• s = "2736"

Step 2: Find minimum value

• The first digit is s[0] = '2'
• Replace all occurrences of '2' with '0': "2736" → "0736"
• Convert to integer: mi = 736

Step 3: Find maximum value

• Iterate through the string to find the first non-'9' digit:
  • s[0] = '2' ✓ (not '9', found it!)
• Replace all occurrences of '2' with '9': "2736" → "9736"
• Convert to integer: maximum = 9736

Step 4: Calculate difference

• Return maximum - mi = 9736 - 736 = 9000

Let's trace through another example where the first digit is already '9': num = 9288

Step 1: s = "9288"

Step 2: Find minimum

• First digit is '9'
• Replace all '9's with '0': "9288" → "0288"
• mi = 288

Step 3: Find maximum

• Iterate to find first non-'9' digit:
  • s[0] = '9' (skip, already '9')
  • s[1] = '2' ✓ (found it!)
• Replace all '2's with '9': "9288" → "9988"
• maximum = 9988

Step 4: Return 9988 - 288 = 9700

The algorithm efficiently finds the optimal digit to remap in each case by using the greedy strategy of choosing the leftmost impactful digit.

Solution Implementation

Time and Space Complexity

The time complexity is O(log n), where n is the value of the number num. This is because:

• Converting the integer to a string takes O(log n) time since the number of digits in num is proportional to log n
• The string replacement operation s.replace() needs to traverse the entire string, which has length O(log n)
• The loop iterates through each character in the string s, which is O(log n) iterations
• Converting the string back to an integer also takes O(log n) time

The space complexity is O(log n), where n is the value of the number num. This is because:

• The string representation s of the number requires O(log n) space to store all the digits
• The string replacement operations create new strings which also require O(log n) space

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Handling Leading Zeros Correctly

The Issue: A common mistake is overthinking the handling of leading zeros. Developers might try to avoid replacing the first digit with '0' thinking it would create an invalid number or require special handling.

Why It Happens: In many programming contexts, we're taught that numbers shouldn't have leading zeros (except for zero itself). This leads to unnecessary complexity where developers might:

• Skip the first digit when looking for a digit to replace with '0'
• Add conditional logic to check if the first digit is being replaced
• Try to find the "second-best" option for minimization

Example of Incorrect Approach:

# INCORRECT - Trying to avoid leading zeros
def minMaxDifference(self, num: int) -> int:
    num_str = str(num)
  
    # Wrong: Trying to find a non-first digit to replace with '0'
    min_value = num
    for i in range(1, len(num_str)):  # Starting from index 1
        if num_str[i] != '0':
            min_value = int(num_str.replace(num_str[i], '0'))
            break
  
    # ... rest of the code

The Solution: Python's int() function automatically handles leading zeros correctly. When you convert a string like "00890" to an integer, Python correctly interprets it as 890. The original solution correctly leverages this:

# CORRECT - Let Python handle leading zeros
min_value = int(num_str.replace(num_str[0], '0'))

Pitfall 2: Replacing Digits That Are Already Optimal

The Issue: Another mistake is not recognizing when a replacement wouldn't improve the result. For example, replacing '9' with '9' for maximization or '0' with '0' for minimization.

Why It Happens: Developers might forget that:

• If the first digit is already '0', replacing it with '0' doesn't minimize further
• If all digits are '9', no replacement can maximize the number further

Example Scenario:

• Input: num = 9999
• The loop looking for a non-'9' digit completes without finding one
• Without the final return statement, the code would fail

The Solution: The code handles this elegantly:

1. For minimization: Even if the first digit is '0', replacing '0' with '0' is valid (just returns the same number)
2. For maximization: The code explicitly checks if all digits are '9' and returns num - min_value in that case

Pitfall 3: Incorrect Understanding of "ALL Occurrences"

The Issue: Some developers might try to replace only the first occurrence of a digit or implement custom logic to selectively replace digits.

Example of Incorrect Understanding:

# INCORRECT - Replacing only one occurrence
def minMaxDifference(self, num: int) -> int:
    num_str = str(num)
  
    # Wrong: Trying to replace only the first '1' with '0'
    min_value = int(num_str[:1].replace('1', '0') + num_str[1:])
    # This would give "01891" = 1891 instead of "00890" = 890

The Solution: Use Python's built-in str.replace() method which replaces ALL occurrences by default:

# CORRECT - Replaces all occurrences
min_value = int(num_str.replace(num_str[0], '0'))

This ensures that when we choose to remap digit '1' to '0' in "11891", we get "00890" (all 1s become 0s), not "01891" (only first 1 becomes 0).