#2566

Easy

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximum Difference by Remapping a Digit

Find the largest difference by remapping a single digit in a number using a greedy approach to maximize and minimize outcomes.

math greedy

Problem Statement

You are given a positive integer num. Bob can remap exactly one digit from 0 to 9 to another digit and create a new number. Your task is to determine how much the value can change after such a remapping.

Return the difference between the maximum and minimum numbers Bob can produce by remapping exactly one digit. Ensure your solution considers the impact of leading digits and uses a greedy choice to select which digit to remap for the largest difference.

Examples

Example 1

Input: num = 11891

Output: 99009

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

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 <= 108

Solution Approach

Maximizing the Number

Scan from the most significant digit and select the first digit that is not 9. Remap all occurrences of this digit to 9 to achieve the maximum possible value. This greedy choice ensures the largest increase without violating number constraints.

Minimizing the Number

For the minimum, examine the first digit. If it's greater than 1, remap it to 1; otherwise, find the first non-zero digit elsewhere and remap it to 0. This preserves the number of digits while producing the smallest valid number.

Calculating the Difference

Once the maximum and minimum numbers are generated, subtract the minimum from the maximum to get the desired difference. This direct computation follows the greedy remapping strategy and gives the correct result efficiently.

Complexity Analysis

Metric	Value
Time	O(\log \textit{num})
Space	O(\log \textit{num})

The algorithm processes each digit once, resulting in O(log num) time complexity. Space complexity is also O(log num) because we store the number as a string for easy manipulation of digits.

What Interviewers Usually Probe

Check for off-by-one errors when remapping the first digit.
Consider numbers with repeated digits and how remapping affects multiple positions.
Verify handling of leading zeros in the minimized number to avoid invalid results.

Common Pitfalls or Variants

Common pitfalls

Attempting to remap digits that do not maximize or minimize the number.
Ignoring the effect of leading digits and accidentally producing an invalid number.
Failing to consider multiple occurrences of the same digit for a consistent remapping.

Follow-up variants

Allow remapping multiple digits instead of only one for maximum impact.
Calculate the difference if remapping must not produce a leading zero.
Extend to negative numbers with similar remapping rules.

FAQ

What is the key pattern in Maximum Difference by Remapping a Digit?

The main pattern is a greedy choice plus invariant validation: select the first digit to remap to maximize or minimize the number while preserving length.

Can multiple digits be remapped in this problem?

No, the problem restricts you to remapping exactly one digit. Attempting multiple remaps changes the rules and results.

How do leading zeros affect the solution?

Leading zeros are invalid, so when minimizing, avoid remapping the first digit to zero. Choose a later non-zero digit if necessary.

What is the time complexity of the greedy solution?

Time complexity is O(log num) because each digit is processed once to determine the maximum and minimum remapping.

Why does remapping the first non-nine digit maximize the number?

Changing the first non-nine digit to 9 produces the largest increase possible without altering the number of digits, following the greedy approach.

terminal

Solution

Solution 1: Greedy

First, we convert the number to a string $s$.

1

2

3

4

5

6

7

8

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        mi = int(s.replace(s[0], '0'))
        for c in s:
            if c != '9':
                return int(s.replace(c, '9')) - mi
        return num - mi

Continue Practicing

#2578 split with minimum sum #2541 minimum operations to make array equal ii #2591 distribute money to maximum children