Max Difference You Can Get From Changing an Integer
MedPrompt
You are given an integer num. You will apply the following steps to num two separate times:
- Pick a digit
x (0 <= x <= 9). - Pick another digit
y (0 <= y <= 9). Noteycan be equal tox. - Replace all the occurrences of
xin the decimal representation ofnumbyy.
Let a and b be the two results from applying the operation to num independently.
Return the max difference between a and b.
Note that neither a nor b may have any leading zeros, and must not be 0.
Example 1:
Input: num = 555
Output: 888
Explanation: 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 = 888Example 2:
Input: num = 9
Output: 8
Explanation: 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
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores all possible transformations of the number num. A transformation is defined by choosing a digit x (0-9) to be replaced and a digit y (0-9) to replace it with. We generate all possible valid numbers by trying every pair of (x, y) and find the maximum and minimum among them.
Algorithm
- Initialize
max_valandmin_valwith the inputnum. - Convert
numto its string representation,s. - Loop through
xfrom '0' to '9' (digit to be replaced). - Inside, loop through
yfrom '0' to '9' (replacement digit). - Apply the replacement to get
newS. - Check if
newSis a valid number (no leading zeros, not zero). - If valid, parse it to an integer
current_val. - Update
max_val = Math.max(max_val, current_val). - Update
min_val = Math.min(min_val, current_val). - Return
max_val - min_val.
Walkthrough
This approach systematically tries every possible transformation to find the maximum and minimum possible outcomes. A transformation is defined by picking a digit x (from 0 to 9) and a replacement digit y (from 0 to 9).
The algorithm iterates through all 100 possible (x, y) pairs. For each pair, it applies the transformation to the original number num. It keeps track of the maximum and minimum valid numbers generated throughout this process. A generated number is valid if it does not have a leading zero (unless it is the number 0 itself, which is not possible here as num >= 1 and results must not be 0).
The final result is the difference between the overall maximum and minimum values found, which corresponds to max(a) - min(b).
public int maxDiff(int num) { String s = Integer.toString(num); int maxVal = num; int minVal = num; for (char x = '0'; x <= '9'; x++) { for (char y = '0'; y <= '9'; y++) { String newS = s.replace(x, y); // Check for invalid leading zeros if (newS.charAt(0) == '0' && newS.length() > 1) { continue; } int currentVal = Integer.parseInt(newS); // The problem states the result must not be 0 if (currentVal == 0) { continue; } maxVal = Math.max(maxVal, currentVal); minVal = Math.min(minVal, currentVal); } } return maxVal - minVal;}Complexity
Time
O(d), where `d` is the number of digits in `num`. The two loops for `x` and `y` run a constant 100 times. String operations inside the loop take O(d) time.
Space
O(d) to store the string representation of the number and its transformations, where `d` is the number of digits in `num`.
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to be correct as it checks all possibilities.
Cons
Performs many redundant and unnecessary computations.
Less efficient due to a large constant factor (100) compared to a targeted approach.
To maximize the difference a - b, we can maximize a and minimize b independently using a greedy strategy. This involves making the most impactful change at the most significant digit possible for both maximization and minimization, while respecting the problem's constraints.
Algorithm
- To find the maximum value
a:- Find the first digit from the left that is not '9'.
- Replace all occurrences of this digit with '9'.
- If all digits are '9',
ais the original number.
- To find the minimum value
b:- If the first digit is not '1', replace all its occurrences with '1'.
- If the first digit is '1', find the first subsequent digit that is not '0' or '1'.
- Replace all occurrences of this digit with '0'.
- If no such digit exists in the second case,
bis the original number.
- Calculate
aandbusing these rules and returna - b.
Walkthrough
This approach directly constructs the optimal numbers a and b to maximize their difference.
Finding the Maximum Value a
To get the maximum possible number, we want to make the most significant change possible. This means changing a digit to 9. The largest increase is achieved by changing the leftmost possible digit. So, we find the first digit from the left that is not 9. Let's call this digit x. We then replace all occurrences of x with 9. If all digits are already 9, no change can increase the number, so a is just the original number.
Finding the Minimum Value b
To get the minimum possible number, we want to make the most significant change downwards. The target replacement digits are 1 (for the leading digit) or 0 (for other digits).
- Case 1: The first digit is not '1'. We can achieve the biggest decrease by changing this most significant digit to '1'. So, we take the first digit
xand replace all its occurrences with '1'. - Case 2: The first digit is '1'. We cannot change it to '0' because that would create an invalid number with a leading zero. So, we must keep the leading '1'. We then scan the rest of the digits from left to right to find the first digit that is not '0' or '1'. Let this digit be
y. We can replace all occurrences ofywith '0' to get the minimum number. If all subsequent digits are '0's or '1's, no change can make the number smaller, sobis the original number.
class Solution { public int maxDiff(int num) { String s = Integer.toString(num); int a = getMax(s); int b = getMin(s); return a - b; } private int getMax(String s) { char x = ' '; // Find the first digit that is not '9' for (char c : s.toCharArray()) { if (c != '9') { x = c; break; } } // If all digits are '9', no change is needed if (x == ' ') { return Integer.parseInt(s); } // Replace all occurrences of x with '9' String newS = s.replace(x, '9'); return Integer.parseInt(newS); } private int getMin(String s) { char firstDigit = s.charAt(0); // Case 1: First digit is not '1' if (firstDigit != '1') { String newS = s.replace(firstDigit, '1'); return Integer.parseInt(newS); } else { // Case 2: First digit is '1' char y = ' '; // Find the first digit after the first that is not '0' or '1' for (int i = 1; i < s.length(); i++) { char c = s.charAt(i); if (c != '0' && c != '1') { y = c; break; } } // If no such digit is found, no change is needed if (y == ' ') { return Integer.parseInt(s); } // Replace all occurrences of y with '0' String newS = s.replace(y, '0'); return Integer.parseInt(newS); } }}Complexity
Time
O(d), where `d` is the number of digits in `num`. The solution involves a few linear scans of the number's string representation.
Space
O(d), where `d` is the number of digits in `num`. This is for storing the string representation of the number.
Trade-offs
Pros
Very efficient, as it directly constructs the optimal numbers
aandb.Avoids unnecessary computations by using a targeted, logical approach.
Cons
The logic is more complex and requires careful handling of multiple cases and edge conditions (e.g., leading '1's, all '9's).
Solutions
Solution
class Solution {public int maxDiff(int num) { String a = String.valueOf(num); String b = a; for (int i = 0; i < a.length(); ++i) { if (a.charAt(i) != '9') { a = a.replace(a.charAt(i), '9'); break; } } if (b.charAt(0) != '1') { b = b.replace(b.charAt(0), '1'); } else { for (int i = 1; i < b.length(); ++i) { if (b.charAt(i) != '0' && b.charAt(i) != '1') { b = b.replace(b.charAt(i), '0'); break; } } } return Integer.parseInt(a) - Integer.parseInt(b); }}class Solution {public: int maxDiff(int num) { auto replace = [](string &s, char a, char b) { for (auto &c : s) { if (c == a) { c = b; } } }; string a = to_string(num); string b = a; for (int i = 0; i < a.size(); ++i) { if (a[i] != '9') { replace(a, a[i], '9'); break; } } if (b[0] != '1') { replace(b, b[0], '1'); } else { for (int i = 1; i < b.size(); ++i) { if (b[i] != '0' && b[i] != '1') { replace(b, b[i], '0'); break; } } } return stoi(a) - stoi(b); }};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)Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.