2566. Maximum Difference by Remapping a Digit

Problem Description

In this problem, we are given an integer num, and we are told that Danny will remap exactly one of the 10 digits (0 through 9) to another digit. Remapping a digit d1 to d2 means replacing all occurrences of d1 in num with d2. We need to calculate the difference between the largest and smallest numbers that can be created by remapping exactly one digit. A couple of important rules to note:

Danny can choose to change a digit to the same digit (effectively not changing the number).
Danny may remap a digit differently when seeking to create the maximum value and minimum value.
The remapped number is allowed to have leading zeros.
The goal is to maximize and minimize the given number separately by changing only one digit and then find the difference between these two values.

Intuition

To find the minimum number, we should look to replace a non-zero digit with 0. The best candidate here is the first non-zero digit, and it should be turned into a zero to minimize the number, taking into account the possibility of leading zeros.

For the maximum number, we aim to replace a digit with 9. However, we must be strategic in choosing which digit to replace:

We can ignore any 9s in the number since changing them to 9 would be redundant.
If there's any digit in the number other than 9, we replace the first occurrence of such a digit with 9 to maximize the number. It's crucial to note that we don't need to look at the rest of the digits once we've performed this remapping since no further changes could create a larger number.

The solution presented checks each digit from the start. It first sets the minimum by replacing the first digit with 0. Then, it iterates through each digit, and upon finding a digit that is not 9, it replaces all occurrences of this digit with 9 to find the maximum number. Finally, it returns the difference between the max value obtained and the min value.

This approach works because of the constraints that we only need to remap a single digit, we want to maximize/minimize with one replacement, and we have the freedom to choose different digits when optimizing for the maximum and minimum values.

Learn more about Greedy and Math patterns.

Solution Approach

The solution approach for this problem is straightforward and cleverly optimizes the search for the maximum and minimum values by remapping only the necessary characters.

Conversion to String: Initially, the integer num is converted into a string. This allows for easy access to its individual digits and simplifies the process of remapping them.
Calculating Minimum: To calculate the minimum possible number, the solution replaces the first digit in the string with 0 (using Python's str.replace() method). This remapped minimum number will be used later to compute the final difference.
Iterative Search for Maximum: The code then uses a for-loop to iterate through each character in the string representation of num. The digits are checked in order, from left to right:
- If a character is found that's not 9, the solution replaces all occurrences of this specific character with 9. After this operation, the maximum possible number is found, and the algorithm stops searching further digits because we've achieved the largest increase possible by changing just one type of digit.
- If it iterates through all digits and they are all 9's, it implies that no increase can occur, hence the maximum number is the same as num.
Returning the Difference: After finding the maximum and minimum values, the function subtracts the minimum from the maximum and returns the resulting difference.

This solution uses the following concepts:

String manipulation and processing: It navigates through the string representation of the integer for both the minimum and maximum calculations, utilizing the fact that strings are easily iterable.
Greedy approach: Remapping the first non-zero for minimum and the first non-nine digit for maximum value ensures we're making the locally optimal choice to minimize or maximize the number. Given the problem constraints, these local choices are also globally optimal.
Conditional logic: By using if-conditions, the algorithm checks for the condition that ensures the maximum increase when replacing a digit with 9.

The elegancy of this algorithm is its simplicity, as it avoids the need for complex data structures or patterns, and performs its task by the simple but efficient traversal of the string.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's demonstrate how the solution approach works with a small example. Suppose we are given the integer num = 682. We need to find the largest and smallest numbers by remapping exactly one digit and then calculate the difference between these two remapped numbers.

Step 1: Conversion to String

First, we convert num to a string: num_str = '682'.

Step 2: Calculating Minimum

Next, to calculate the minimum number, we look for the first non-zero digit. In num_str, this is 6. We then replace this digit with 0, resulting in a new string: min_str = '082'. This is our minimum number with leading zeros allowed, which evaluates to 82.

Step 3: Iterative Search for Maximum

Now, we iterate through num_str to find the first digit that is not 9 and replace all occurrences of this digit with 9. Starting from the left, 6 is not a 9, so we replace it: max_str = '982'. We stop after this replacement because we are only allowed to remap one digit, and we've created the largest number possible by doing so, which is 982.

Step 4: Returning the Difference

Finally, we convert min_str and max_str back to integers and subtract to get the difference: max_num = 982, min_num = 82, so the difference is 900.

In this example, by strategically remapping 6 to 0 for the minimum and 6 to 9 for the maximum, we've maximized the difference to 900.

Solution Implementation

1class Solution:
2    def minMaxDifference(self, num: int) -> int:
3        # Convert the given integer to a string for processing
4        num_str = str(num)
5      
6        # Replace the first digit of the string with '0' to create the minimum number
7        # This works under the assumption that the first digit is not '0'
8        # Otherwise, 'mi' would become a different number of digits.
9        min_num = int(num_str.replace(num_str[0], '0'))
10      
11        # Iterate over the digits of the string
12        for digit in num_str:
13            # If a digit is not '9', we can create the max number
14            # by replacing the first occurrence of that digit with '9'
15            if digit != '9':
16                max_num = int(num_str.replace(digit, '9'))
17                # Return the difference between the max number and the min number
18                return max_num - min_num
19              
20        # If all digits are '9', return the difference between the original number and min_num
21        return num - min_num
22

1class Solution {
2    public int minMaxDifference(int num) {
3        String numStr = String.valueOf(num); // Convert the integer to a string for manipulation
4        int minVal = Integer.parseInt(numStr.replace(numStr.charAt(0), '0')); // Replace first digit with '0' to get the minimum value
5        // Iterate over the characters in the string
6        for (char digit : numStr.toCharArray()) {
7            if (digit != '9') {
8                // Replace the current digit with '9' to get the maximum value and return the difference
9                return Integer.parseInt(numStr.replace(digit, '9')) - minVal;
10            }
11        }
12        // If all digits are '9', return the difference between the original number and minVal
13        return num - minVal;
14    }
15}
16

1class Solution {
2public:
3    // Function to calculate the minimum and maximum difference by altering numbers
4    int minMaxDifference(int num) {
5        // Convert the input number to a string
6        string numStr = to_string(num);
7
8        // Create a copy of the string for later modification
9        string maxStr = numStr;
10
11        // Get the first digit of the string
12        char firstDigit = numStr[0];
13
14        // Replace all occurrences of the first digit with '0' to create the minimum possible number
15        for (char& c : numStr) {
16            if (c == firstDigit) {
17                c = '0';
18            }
19        }
20
21        // Convert the modified string back to an integer to obtain the minimum number
22        int minNum = stoi(numStr);
23
24        // Iterate over the characters in the copy of the original number string
25        for (int i = 0; i < maxStr.size(); ++i) {
26            // If a character is not '9', it can be replaced with '9' to maximize the number
27            if (maxStr[i] != '9') {
28                char currentDigit = maxStr[i];
29
30                // Replace all occurrences of the current digit with '9'
31                for (int j = i; j < maxStr.size(); ++j) {
32                    if (maxStr[j] == currentDigit) {
33                        maxStr[j] = '9';
34                    }
35                }
36
37                // Convert the maximized string back to an integer and return the difference
38                return stoi(maxStr) - minNum;
39            }
40        }
41
42        // If all characters were '9', return the difference between the original number and the minimum number
43        return num - minNum;
44    }
45};
46

1function minMaxDifference(num: number): number {
2    // Convert the number to a string.
3    const numString = num.toString();
4
5    // Replace the first digit of the number with '0's to find the minimum.
6    const min = Number(numString.replace(new RegExp(numString[0], 'g'), '0'));
7
8    // Iterate through the string representation of the number.
9    for (const digit of numString) {
10        // If the current digit is not '9', replace all occurrences of this digit
11        // with '9's to get the maximum number and return the difference.
12        if (digit !== '9') {
13            const max = Number(numString.replace(new RegExp(digit, 'g'), '9'));
14            return max - min;
15        }
16    }
17
18    // In the case where all digits are '9's, the max is the number itself; return the difference.
19    return num - min;
20}
21

Time and Space Complexity

Time Complexity

The time complexity of the function minMaxDifference can be analyzed by looking at the operations that are executed in sequence:

The conversion of num into a string s is O(n), where n is the number of digits in num, because each digit has to be processed.
The replacement operation to create mi, which runs in O(n) since in the worst case, it has to check each character to perform the replacement.
The for-loop iterates over each character in the string s once, resulting in O(n) complexity.
Inside the loop, a replacement operation is done and can be considered O(n). In the worst case, this runs only once because the function returns immediately after finding the first character that is not '9'.

Since the steps mentioned above are executed sequentially, and the loop has an early return condition, the time complexity of the code is O(n) – linear with respect to the number of digits in num.

Space Complexity

The space complexity of the function is determined by the extra space used by the variables s and mi, as well as the space for any intermediate strings created during the replace operations:

The space required to store the string s is O(n).
The integer mi does not depend on n and is thus O(1).
The replacement operation creates a new string each time it is called, but since these strings are not stored and only one exists at any time, the additional space complexity is O(n).

Therefore, the overall space complexity of the function is O(n), which again is linear with respect to the number of digits in num.

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the following is a good use case for backtracking?

Combinatorial problems

Random number generation

Topological sorting

Matrix multiplication

I don’t know