#1432

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Max Difference You Can Get From Changing an Integer

Compute the maximum difference from changing digits in an integer using greedy choices and invariant checks efficiently.

math greedy

Problem Statement

Given an integer num, you can independently choose a digit x in num and replace all its occurrences with another digit y (0-9) to form a new integer. Repeat this process twice, storing the results as a and b.

Return the maximum difference possible between the two resulting integers a and b. The operation must maintain the integer's structure and avoid leading zeros when calculating the minimum transformation.

Examples

Example 1

Input: num = 555

Output: 888

The first time pick x = 5 and y = 9 and store the new integer in a. The second time pick x = 5 and y = 1 and store the new integer in b. We have now a = 999 and b = 111 and max difference = 888

Example 2

Input: num = 9

Output: 8

The first time pick x = 9 and y = 9 and store the new integer in a. The second time pick x = 9 and y = 1 and store the new integer in b. We have now a = 9 and b = 1 and max difference = 8

Constraints

1 <= num <= 108

Solution Approach

Identify the greedy choices

To maximize the integer, select the first non-9 digit and replace all its occurrences with 9. To minimize, replace the first non-1 (or leading non-zero) digit with 1 to avoid invalid numbers. These choices directly target the largest achievable difference.

Perform invariant validation

Ensure that when minimizing, the resulting number does not start with zero and maintains the same number of digits. Similarly, validate that maximizing does not create any unintended structural issues. This preserves the integer's integrity while changing digits.

Calculate the max difference

After generating a and b independently using the greedy transformations, subtract b from a to compute the maximum difference. This single computation gives the correct answer without iterating through all digit replacements.

Complexity Analysis

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

Time complexity is O(\log(\textit{num})) because the number of digits in num determines the operations. Space complexity is O(\log(\textit{num})) for storing the transformed strings of digits.

What Interviewers Usually Probe

Check whether candidates correctly identify which digit to change to maximize and minimize independently.
Listen for mention of maintaining number validity while applying greedy choices.
Look for reasoning about why replacing all occurrences of a digit gives the largest difference efficiently.

Common Pitfalls or Variants

Common pitfalls

Attempting to replace digits without considering leading zeros when minimizing.
Overcomplicating by iterating through every possible digit replacement instead of greedy selection.
Failing to apply the operation independently twice, leading to incorrect difference calculation.

Follow-up variants

Compute maximum difference if only a single replacement is allowed instead of two independent operations.
Allow negative integers and compute the maximum difference with the same greedy principle.
Restrict replacements to adjacent digits only and observe how greedy choices adapt.

FAQ

What is the key pattern for Max Difference You Can Get From Changing an Integer?

The main pattern is greedy choice plus invariant validation, where you change digits independently to find max and min values.

Why can't I just change any digit to 0 when minimizing?

Changing the leading digit to 0 can produce an invalid integer, so the invariant check ensures the number remains valid.

How do I know which digit to change to maximize the difference?

Pick the first non-9 digit to replace with 9 for maximization, and the first suitable digit for minimization while avoiding leading zeros.

What is the time complexity of this solution?

It is O(\log(\textit{num})), proportional to the number of digits in the input integer.

Can this approach handle large integers up to 10^8?

Yes, because it only processes digits individually, ensuring linear work relative to the number of digits.

terminal

Solution

Solution 1: Greedy

To obtain the maximum difference, we should take the maximum and minimum values, as this yields the largest difference.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def maxDiff(self, num: int) -> int:
        a, b = str(num), str(num)
        for c in a:
            if c != "9":
                a = a.replace(c, "9")
                break
        if b[0] != "1":
            b = b.replace(b[0], "1")
        else:
            for c in b[1:]:
                if c not in "01":
                    b = b.replace(c, "0")
                    break
        return int(a) - int(b)

Continue Practicing

#1414 find the minimum number of fibonacci numbers whose sum is k #1363 largest multiple of three #1330 reverse subarray to maximize array value