Maximum Difference by Remapping a Digit
EasyPrompt
You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.
Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.
Notes:
- When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of
d1innumwithd2. - Bob can remap a digit to itself, in which case
numdoes not change. - Bob can remap different digits for obtaining minimum and maximum values respectively.
- The resulting number after remapping can contain leading zeroes.
Example 1:
Input: num = 11891
Output: 99009
Explanation:
To achieve the maximum value, Bob can remap the digit 1 to the digit 9 to yield 99899.
To achieve the minimum value, Bob can remap the digit 1 to the digit 0, yielding 890.
The difference between these two numbers is 99009.Example 2:
Input: num = 90
Output: 99
Explanation:
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
Thus, we return 99.
Constraints:
1 <= num <= 108
Approaches
2 approaches with complexity analysis and trade-offs.
This approach exhaustively tries every possible remapping. There are 10 digits to choose from (0-9) and 10 digits to remap to (0-9). We can iterate through all 100 possible pairs of (digit to replace, replacement digit), apply the remapping to the original number, and keep track of the minimum and maximum values encountered.
Algorithm
- Convert the input number
numto its string representation,s. - Initialize
maxValandminValtonum. - Iterate through all possible digits to be replaced,
d1, from '0' to '9'. - Inside this loop, iterate through all possible replacement digits,
d2, from '0' to '9'. - For each pair
(d1, d2), create a new stringtemp_sby replacing all occurrences ofd1inswithd2. - Convert
temp_sto an integercurrentVal. - Update
maxVal = max(maxVal, currentVal). - Update
minVal = min(minVal, currentVal). - After the loops complete, return
maxVal - minVal.
Walkthrough
The core idea is to simulate the process for all 100 possible remappings. We convert the number to a string to make digit replacement easier. We then use two nested loops: the outer loop selects the digit d1 to be replaced (from '0' to '9'), and the inner loop selects the digit d2 to replace it with (from '0' to '9'). In each iteration, we generate a new number by performing the replacement s.replace(d1, d2). This new number is then compared with our running maximum and minimum values, which are updated accordingly. Finally, after checking all possibilities, the difference between the maximum and minimum gives the answer.
Complexity
Time
O(C * L), where C is the number of possible remappings (10 * 10 = 100) and L is the number of digits in `num`. Since C is a constant, this simplifies to O(L), but with a large constant factor.
Space
O(L), where L is the number of digits in `num`. This space is used to store the string representation of the number and the temporary strings created in each iteration.
Trade-offs
Pros
Simple to conceptualize and implement.
Guaranteed to be correct as it explores the entire search space of single-digit remappings.
Cons
Performs many redundant or unnecessary computations. For example, it tries remapping digits that are not present in the input number.
Less efficient due to a large constant factor (100) in its time complexity compared to a direct analytical approach.
Instead of checking all 100 possible remappings, we can analytically determine the single best remapping to achieve the maximum value and the single best remapping for the minimum value. This direct approach is significantly more efficient.
Algorithm
- Convert the input number
numto its string representation,s. - To find the maximum value (
maxVal):- Find the first digit from the left,
x, that is not '9'. - If no such digit exists (all digits are '9'),
maxValis simplynum. - Otherwise, create a new string by replacing all occurrences of
xinswith '9'. - Convert this new string to an integer to get
maxVal.
- Find the first digit from the left,
- To find the minimum value (
minVal):- Take the first digit of
s, let it bey. - Create a new string by replacing all occurrences of
yinswith '0'. - Convert this new string to an integer to get
minVal.
- Take the first digit of
- Return
maxVal - minVal.
Walkthrough
This optimized approach is based on the principle that changes to more significant (leftmost) digits have a greater impact on the number's value.
For the maximum value: To make the number as large as possible, we should change a digit to '9'. To maximize the impact, we should modify the leftmost possible digit. Therefore, we find the first digit from the left that is not '9' and replace all of its occurrences with '9'. If all digits are already '9', the number cannot be increased.
For the minimum value: To make the number as small as possible, we should change a digit to '0'. Again, to maximize the impact (in this case, the decrease in value), we should target the most significant digit. By replacing all occurrences of the very first digit with '0', we achieve the largest possible reduction in value.
By directly calculating these two optimal values and finding their difference, we arrive at the solution much faster than the brute-force method.
class Solution { public int maxDiff(int num) { String s = String.valueOf(num); // Calculate maxVal int maxVal = num; char replaceForMax = ' '; for (char c : s.toCharArray()) { if (c != '9') { replaceForMax = c; break; } } if (replaceForMax != ' ') { maxVal = Integer.parseInt(s.replace(replaceForMax, '9')); } // Calculate minVal char replaceForMin = s.charAt(0); int minVal = Integer.parseInt(s.replace(replaceForMin, '0')); return maxVal - minVal; }}Complexity
Time
O(L), where L is the number of digits in `num`. We perform a few passes over the string representation of the number, resulting in a linear time complexity.
Space
O(L), where L is the number of digits in `num`. Space is required for the string representations of the numbers.
Trade-offs
Pros
Highly efficient with a minimal constant factor.
Avoids unnecessary computations by directly targeting the optimal remappings.
Cons
Requires careful logical deduction to ensure the strategies for finding the max and min values are correct for all edge cases.
Solutions
Solution
class Solution {public int minMaxDifference(int num) { String s = String.valueOf(num); int mi = Integer.parseInt(s.replace(s.charAt(0), '0')); for (char c : s.toCharArray()) { if (c != '9') { return Integer.parseInt(s.replace(c, '9')) - mi; } } return num - mi; }}/** * @param {number} num * @return {number} */ var minMaxDifference = function (num) { const s = num.toString(); const mi = +s.replaceAll(s[0], " 0 "); for (const c of s) { if (c !== " 9 ") { const mx = +s.replaceAll(c, " 9 "); return mx - mi; } } return num - mi; };class Solution {public: int minMaxDifference(int num) { string s = to_string(num); string t = s; char first = s[0]; for (char &c : s) { if (c == first) { c = '0'; } } int mi = stoi(s); for (int i = 0; i < t.size(); ++i) { if (t[i] != '9') { char second = t[i]; for (int j = i; j < t.size(); ++j) { if (t[j] == second) { t[j] = '9'; } } return stoi(t) - mi; } } return num - mi; }};class Solution: def minMaxDifference(self, num: int) -> int: s = str(num) mi = int(s . replace(s[0], '0')) for c in s: if c != '9': return int(s . replace(c, '9')) - mi return num - miVideo 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.