1432. Max Difference You Can Get From Changing an Integer

Problem Description

In the given problem, we have an integer num. We need to perform a series of steps twice in order to generate two different numbers, a and b. The steps are as follows:

Select a digit x within the range of 0 to 9 from the number.
Select another digit y within the range of 0 to 9. Note that y can be the same as x.
Replace all instances of x with y in the number to create a new variant.
Ensure that the resulting number doesn't have any leading zeros and isn't zero itself.

After performing these steps twice, we want to find the maximum difference between the two resulting numbers a and b. The underlying challenge is to decide which digits to replace in order to maximize this difference.

Intuition

The intuition behind the solution involves two primary goals: first, maximize the value of a, and second, minimize the value of b. To increase a as much as possible, we should replace the first non-nine digit (from left to right) with a nine. This ensures the greatest increase in the number's value.

Conversely, to minimize b, we should reduce the value of the first digit if it is not already a one, by replacing it with one. This is because the first digit has the largest weight in determining the value of the number. If the first digit is already a one, we search for the first non-zero and non-one digit to change to zero, since one cannot be replaced with zero (as it would not decrease the number's value). This approach is used because the digit zero gives the lowest possible value, and we want b to be as small as it can be.

Making these replacements produces two numbers, a and b, that are on the opposite ends of the possible range, thus maximizing the difference between them. The code correctly implements this strategy, and by converting the resulting strings back to integers and subtracting b from a, we yield the desired maximum difference.

Learn more about Greedy and Math patterns.

Solution Approach

The implemented solution follows a straightforward approach:

Convert the original number num to a string, so we can conveniently access and replace digits.
To compute a, iterate over the string representation of num to find the first digit that is not 9. Once such a digit is found, replace all instances of this digit with 9 in the string. This guarantees the largest possible increase for a, as replacing any digit with 9 will yield the highest number possible, given the constraint that we change all occurrences of the chosen digit.
For computing b, we look at the first digit of the string representation. If it is not 1, we replace all instances of this first digit with 1. We do this because the leftmost digit carries the most weight in determining the size of the number, and changing it to 1 gives us the largest possible decrease, without violating the constraint that the new integer cannot have leading zeros or be zero.
If the first digit is already 1, we skip it and then iterate through the rest of the digits to find the first digit that isn't 0 or 1 and replace all instances of this digit with 0. This ensures that b becomes the lowest possible number without resulting in a leading zero or turning the number into zero.
After replacement, we convert a and b back to integers and calculate the difference a - b, which represents the maximum possible difference obtained by applying the given operations twice.

The solution effectively uses Python's string manipulation capabilities to replace characters. No complex data structures or algorithms are required, as the problem boils down to making the right choices on which digits to replace during each step.

By making the optimal replacements, the algorithm ensures that the difference between the maximum and minimum possible values after transformation is as large as possible.

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 illustrate the solution approach with a small example where num = 2736. Our goal is to perform the steps mentioned in the solution to maximize the difference between the two resulting numbers a and b.

Step 1: Convert num to a string to handle each digit individually.

num_str = "2736"

Step 2: Maximize the number a.

Iterate over num_str from left to right and find the first digit that is not 9. In this case, it is 2.
Replace all instances of 2 with 9. Our new string for a is "9736".

Step 3: Minimize the number b.

Check the first digit of num_str. It is 2, which is not 1, so we replace it with 1.
However, since we have already replaced 2 with 9 for calculating a, we can't change b the same way.
So, for b, we start from the original num_str which is "2736" and perform replacement:
- The first digit is 2 and not 1, so for b, all instances of 2 are replaced with 1. The new string for b is "1736".

Step 4: Address the case where the first digit is already 1

This step is not applicable to our example, as we have already replaced the first digit with 1 since it was not 1 to begin with.

Step 5: Calculate the difference between a and b.

Convert the new strings "9736" for a and "1736" for b back to integers.
a = 9736
b = 1736
The maximum difference is a - b = 9736 - 1736 = 8000.

By following these steps, the solution has correctly and efficiently maximized the difference between a and b, resulting in a difference of 8000. The ability to identify which digits to replace is key to achieving the optimal result in this scenario.

Solution Implementation

1class Solution:
2    def maxDiff(self, num: int) -> int:
3        # Convert the given number to a string for character manipulation
4        str_num = str(num)
5
6        # Find the maximum number (replace one non '9' digit with '9')
7        max_num = str_num
8        for digit in str_num:
9            if digit != '9':
10                # Replace all instances of the first non '9' digit with '9'
11                max_num = max_num.replace(digit, '9')
12                break  # Break after the first replacement
13
14        # Find the minimum number
15        # If the first digit is not '1', replace all instances of it with '1'
16        min_num = str_num
17        if str_num[0] != '1':
18            min_num = min_num.replace(str_num[0], '1')
19        else:
20            # Otherwise, for the rest of the digits, find the first digit that is not '0' or '1' and replace all instances with '0'
21            for digit in str_num[1:]:
22                if digit not in '01':
23                    min_num = min_num.replace(digit, '0')
24                    break  # Break after the first replacement
25
26        # Return the difference between the maximum and minimum number
27        return int(max_num) - int(min_num)
28

1class Solution {
2  
3    // This method calculates the maximum difference between two numbers 
4    // that can be obtained by changing the digits of the original number.
5    public int maxDiff(int num) {
6        // Convert the integer to a String for easier manipulation.
7        String numStr = String.valueOf(num);
8        // Create two copies of the string, one for the maximum value and one for the minimum.
9        String maxNumStr = numStr;
10        String minNumStr = numStr;
11
12        // Find the first non-'9' digit and replace all its occurrences with '9' to get the maximum number.
13        for (int i = 0; i < numStr.length(); ++i) {
14            if (numStr.charAt(i) != '9') {
15                maxNumStr = numStr.replace(numStr.charAt(i), '9');
16                break;
17            }
18        }
19
20        // For minimum number, if the first digit is not '1', replace all its occurrences with '1'.
21        if (minNumStr.charAt(0) != '1') {
22            minNumStr = minNumStr.replace(minNumStr.charAt(0), '1');
23        } else {
24            // If the first digit is '1', find the first digit that is not '0' or '1' from the second digit onwards
25            // and replace all its occurrences with '0'.
26            for (int i = 1; i < minNumStr.length(); ++i) {
27                if (minNumStr.charAt(i) != '0' && minNumStr.charAt(i) != '1') {
28                    minNumStr = minNumStr.replace(minNumStr.charAt(i), '0');
29                    break;
30                }
31            }
32        }
33      
34        // Parse the max and min strings back to integers and return the difference.
35        return Integer.parseInt(maxNumStr) - Integer.parseInt(minNumStr);
36    }
37}
38

1class Solution {
2public:
3    // Function to replace all occurrences of a character 'from' with 'to' in a string 's'
4    void replaceAll(std::string& s, char from, char to) {
5        for (char& c : s) {
6            if (c == from) {
7                c = to;
8            }
9        }
10    }
11  
12    // Function to calculate the maximum difference between two numbers you can get
13    // by changing digits of the original number 'num'
14    int maxDiff(int num) {
15        // Convert the number to a string for easy manipulation
16        std::string highestNumStr = std::to_string(num);
17        std::string lowestNumStr = highestNumStr;
18      
19        // Crete the highest possible number by replacing the first non '9' digit with '9'
20        for (int i = 0; i < highestNumStr.size(); ++i) {
21            if (highestNumStr[i] != '9') {
22                replaceAll(highestNumStr, highestNumStr[i], '9');
23                break;
24            }
25        }
26      
27        // Create the lowest possible number
28        if (lowestNumStr[0] != '1') {
29            // If the first digit is not '1', replace it with '1'
30            replaceAll(lowestNumStr, lowestNumStr[0], '1');
31        } else {
32            // If the first digit is '1', find the next digit that is not '0' or '1' and replace it with '0'
33            for (int i = 1; i < lowestNumStr.size(); ++i) {
34                if (lowestNumStr[i] != '0' && lowestNumStr[i] != '1') {
35                    replaceAll(lowestNumStr, lowestNumStr[i], '0');
36                    break;
37                }
38            }
39        }
40      
41        // Convert the modified strings back to integers and return the difference
42        return std::stoi(highestNumStr) - std::stoi(lowestNumStr);
43    }
44};
45

1// Function to calculate the maximum difference between two numbers you can get
2// by altering characters of the original number 'num'
3function maxDiff(num: number): number {
4    // Convert the number to a string for easy manipulation
5    let highestNumStr: string = num.toString();
6    let lowestNumStr: string = highestNumStr;
7
8    // Create the highest possible number by replacing the first non '9' digit with '9'
9    for (let i: number = 0; i < highestNumStr.length; ++i) {
10        if (highestNumStr[i] !== '9') {
11            highestNumStr = highestNumStr.replace(highestNumStr[i], '9');
12            // After replacement is done, break out of the loop
13            break;
14        }
15    }
16
17    // Create the lowest possible number
18    if (lowestNumStr[0] !== '1') {
19        // If the first digit is not '1', replace it with '1'
20        lowestNumStr = lowestNumStr.replace(lowestNumStr[0], '1');
21    } else {
22        // If the first digit is '1', find the next digit that is not '0' or '1' and replace it with '0'
23        for (let i: number = 1; i < lowestNumStr.length; ++i) {
24            if (lowestNumStr[i] !== '0' && lowestNumStr[i] !== '1') {
25                lowestNumStr = lowestNumStr.replace(lowestNumStr[i], '0');
26                // After replacement is done, break out of the loop
27                break;
28            }
29        }
30    }
31
32    // Convert the modified strings back to numbers and compute the difference
33    // The difference is returned as the result
34    return parseInt(highestNumStr, 10) - parseInt(lowestNumStr, 10);
35}
36

Time and Space Complexity

The given Python code defines a method maxDiff that computes the maximum difference by transforming the input integer into its greatest and smallest possible values by changing its digits.

Time Complexity:

To determine the time complexity, we consider the length of the string representation of the input number n as d.

The method converts the number to a string twice, which takes O(d) time.
The first for loop iterates over each character in the string a, and in the worst case, this would be d iterations. The replace operation inside the loop can potentially replace d - 1 characters in the worst case, taking O(d) time. However, since the loop breaks after the first replacement, this loop runs at most once, so it is O(d).
There's a similar for loop for string b. The worst-case scenario would be checking each character until the second to last, and performing one replacement operation which also takes O(d) time.

Hence, the overall time complexity of the function is O(d) due to the string manipulation operations being based on the length of the number's string representation.

Space Complexity:

For space complexity, we consider the extra space used by the algorithm besides the input.

Two new string variables a and b are created based on the number's string representation, which consume O(d) space together.
No additional data structures are used that grow with the length of the string representation of the input.

Thus, the space complexity is O(d), where d is the length of the string representation of the number since the space required depends only on the length of the string copies a and b.

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

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know