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

Max Difference You Can Get From Changing an Integer

Number: 1529

Difficulty: Medium

Paid? No

Companies: Mercari

Problem Description

Given an integer num, perform exactly two digit-replacement operations. In each operation, choose a digit x (0 <= x <= 9) from the current number, and choose another digit y (0 <= y <= 9) which could be the same as x, then replace every occurrence of x with y. The resulting number must not have leading zeros and it cannot be 0. Let a be the result from the first operation (intended to maximize the number) and b be the result from the second operation (intended to minimize the number). Return the maximum possible difference a - b.

Key Insights

  • To maximize the number (a), identify the first digit (from left) that is not already 9 and change all of its occurrences to 9.
  • To minimize the number (b), there are two cases:
    • If the first digit is not 1, change all occurrences of that digit to 1.
    • Otherwise, traverse the number from the second digit. Find the first digit that is not 0 or 1 and change all of its occurrences to 0.
  • The operations must ensure that the result does not have a leading zero and is never 0.
  • Both transformations can be done in a single scan of the number’s string representation.

Space and Time Complexity

Time Complexity: O(n), where n is the number of digits in num.
Space Complexity: O(n), due to conversion of the number to a string for processing.

Solution

The problem can be solved by converting the given integer into its string representation. For the maximum number a, scan from left to right until you find a digit other than '9'. Replace all occurrences of that digit with '9'.
For the minimum number b, if the first digit is not '1', replace all of its occurrences with '1'. If the first digit is already '1', scan from the second digit onward and replace all occurrences of the first digit found that isn’t '0' or '1' with '0'.
After obtaining both transformed numbers, convert them back to integers and compute the difference a - b.

The solution uses basic string manipulation and scanning (iteration) methods, which are efficient with a linear time complexity relative to the number of digits.

Code Solutions

# Python solution for the problem

def maxDiff(num):
    # Convert number to string for easier manipulation
    num_str = str(num)
    
    # Create a helper function to replace all occurrences of a given digit in the string
    def replace_all(s, char_to_replace, replacement):
        result = ""
        for ch in s:
            if ch == char_to_replace:
                result += replacement
            else:
                result += ch
        return result

    # Find the maximum number (a) by replacing first non-'9' digit with '9'
    max_num_str = num_str  # Default value if no changes are needed
    for ch in num_str:
        if ch != '9':
            # Once a non-'9' digit is found, replace every occurrence with '9'
            digit_to_replace = ch
            max_num_str = replace_all(num_str, digit_to_replace, '9')
            break

    # Find the minimum number (b)
    min_num_str = num_str  # Default value if no changes can be made
    # Case 1: If the first digit is not '1', replace all its occurrences with '1'
    if num_str[0] != '1':
        digit_to_replace = num_str[0]
        min_num_str = replace_all(num_str, digit_to_replace, '1')
    else:
        # Case 2: Otherwise, check the rest of the digits for a candidate digit that is not '0' or '1'
        for ch in num_str[1:]:
            if ch != '0' and ch != '1':
                digit_to_replace = ch
                min_num_str = replace_all(num_str, digit_to_replace, '0')
                break

    # Convert the modified strings back to integers and return the difference
    return int(max_num_str) - int(min_num_str)

# Example usage:
print(maxDiff(555))  # Expected output: 888
print(maxDiff(9))    # Expected output: 8
← Back to All Questions