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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Difference by Remapping a Digit

Number: 2704

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

We are given an integer num. Bob can remap exactly one digit (i.e. change all occurrences of one chosen digit to another digit between 0 and 9) in num. The goal is to find the difference between the maximum and minimum values Bob can achieve through such a remapping. Note that the modifications can result in numbers with leading zeros.

Key Insights

  • To maximize the value, replace the first digit that is not '9' with '9' everywhere in the number.
  • To minimize the value, there are two scenarios:
    • If the leading digit is not '1', replace it with '1'.
    • Otherwise, find the first digit (other than the leading one) that is not '0' or '1' and replace all its occurrences with '0'.
  • String conversion and manipulation simplifies replacing digits and evaluating the resulting values.

Space and Time Complexity

Time Complexity: O(n), where n is the number of digits in num
Space Complexity: O(n), for storing the string representation of num

Solution

Convert the integer num into its string representation. For obtaining the maximum value, iterate over the string from left to right and find the first digit that is not '9' and replace every occurrence of that digit with '9'. For obtaining the minimum value, check if the first digit is not '1' and if so, replace all its occurrences with '1'. Otherwise, find the first digit (after the first character) that is not '0' or '1' and replace every occurrence of that digit with '0'. Finally, convert the new strings back into integers and return the difference between the maximum and minimum values.

Code Solutions

# Python solution with detailed comments
def max_diff(num):
    num_str = str(num)
    
    # Compute maximum value by replacing the first non-'9' digit with '9'
    max_num_str = num_str
    for digit in num_str:
        if digit != '9':
            max_num_str = num_str.replace(digit, '9')
            break
    max_val = int(max_num_str)
    
    # Compute minimum value by remapping one digit
    min_num_str = num_str
    # If the first digit is not '1', replace it with '1' everywhere
    if num_str[0] != '1':
        min_num_str = num_str.replace(num_str[0], '1')
    else:
        # Otherwise, find the first digit (after the first) that is not '0' or '1'
        for digit in num_str[1:]:
            if digit != '0' and digit != '1':
                min_num_str = num_str.replace(digit, '0')
                break
    min_val = int(min_num_str)
    
    return max_val - min_val

# Example usage:
print(max_diff(11891))  # Expected output: 99009
print(max_diff(90))     # Expected output: 99
← Back to All Questions