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 thaty
can be the same asx
. - Replace all instances of
x
withy
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.
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 ofnum
to find the first digit that is not9
. Once such a digit is found, replace all instances of this digit with9
in the string. This guarantees the largest possible increase fora
, as replacing any digit with9
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 not1
, we replace all instances of this first digit with1
. We do this because the leftmost digit carries the most weight in determining the size of the number, and changing it to1
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't0
or1
and replace all instances of this digit with0
. This ensures thatb
becomes the lowest possible number without resulting in a leading zero or turning the number into zero. -
After replacement, we convert
a
andb
back to integers and calculate the differencea - 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 EvaluatorExample 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 not9
. In this case, it is2
. - Replace all instances of
2
with9
. Our new string fora
is"9736"
.
Step 3: Minimize the number b
.
- Check the first digit of
num_str
. It is2
, which is not1
, so we replace it with1
. - However, since we have already replaced
2
with9
for calculatinga
, we can't changeb
the same way. - So, for
b
, we start from the originalnum_str
which is"2736"
and perform replacement:- The first digit is
2
and not1
, so forb
, all instances of2
are replaced with1
. The new string forb
is"1736"
.
- The first digit is
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 not1
to begin with.
Step 5: Calculate the difference between a
and b
.
- Convert the new strings
"9736"
fora
and"1736"
forb
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 stringa
, and in the worst case, this would bed
iterations. Thereplace
operation inside the loop can potentially replaced - 1
characters in the worst case, takingO(d)
time. However, since the loop breaks after the first replacement, this loop runs at most once, so it isO(d)
. - There's a similar
for
loop for stringb
. The worst-case scenario would be checking each character until the second to last, and performing one replacement operation which also takesO(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
andb
are created based on the number's string representation, which consumeO(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.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!