Maximum Difference by Remapping a Digit — Problem & Solution
Maximum Difference by Remapping a Digit solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Maximum Difference by Remapping a Digit is an easy coding problem on math and greedy, asked in Amazon, Adobe and Zoho interviews.
- Difficulty: Easy
- Topics: Math, Greedy
- Asked at: Amazon, Adobe, Zoho
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Pick one digit d and one digit e (possibly the same) and replace every occurrence of d in num with e. Leading zeros are allowed in the result.
Do this once to get the largest possible value and once to get the smallest, and return the difference.
Example 1
Input: num = 11891
Output: 99009
Explanation: Mapping 1 → 9 gives 99899; mapping 1 → 0 gives 00890, i.e. 890.
Example 2
Input: num = 90
Output: 99
Explanation: Mapping 0 → 9 gives 99; mapping 9 → 0 gives 00.
Example 3
Input: num = 999
Output: 999
Explanation: Already maximal; mapping 9 → 0 gives 0.
Constraints
1 <= num <= 1000000000
Hints for Maximum Difference by Remapping a Digit
Hint 1
For the maximum, turn the leftmost non-9 digit into 9 — changing an earlier digit is worth more than any later one.
Hint 2
For the minimum, turn the leading digit into 0.
Hint 3
Every occurrence of the chosen digit changes, which is what makes the leftmost choice the right one.
How to solve Maximum Difference by Remapping a Digit
Place value decides everything: raising the most significant digit that can be raised beats any change further right, and lowering the leading digit to 0 is the biggest possible reduction.
Approach
- Render
numas a string. - For the maximum, find the first character that is not
'9'and replace every copy of it with'9'; if there is none, the number is already maximal. - For the minimum, replace every copy of the leading character with
'0'. - Return the difference of the two parsed values.
Why it works
Changing a digit at position i alters the value by at least 10^(len-1-i), which dominates any change at a later position — so the leftmost changeable digit is the one to pick. Mapping it to 9 is the largest increase available and mapping the leading digit to 0 the largest decrease; other occurrences of the same digit only help, since they move in the same direction.
Complexity
- Time —
O(d) in the number of digits - Space —
O(d)
Pitfalls
- A number of all 9s has no digit to raise — the maximum is the number itself.
- Leading zeros are permitted, so
"00890"parses to 890 rather than being rejected. - The replacement is global: every copy of the chosen digit changes, not just the first.
Reference solution
Python
def minMaxDifference(num: int) -> int:
s = str(num)
hi = s
for ch in s:
if ch != "9":
hi = s.replace(ch, "9")
break
lo = s.replace(s[0], "0")
return int(hi) - int(lo)Java
public static int minMaxDifference(int num) {
String s = Integer.toString(num);
String hi = s;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) != '9') {
hi = s.replace(s.charAt(i), '9');
break;
}
}
String lo = s.replace(s.charAt(0), '0');
return Integer.parseInt(hi) - Integer.parseInt(lo);
}C++
int minMaxDifference(int num) {
string s = to_string(num);
string hi = s;
for (int i = 0; i < (int) s.size(); i++) {
if (s[i] != '9') {
char d = s[i];
hi = s;
for (int j = 0; j < (int) hi.size(); j++) if (hi[j] == d) hi[j] = '9';
break;
}
}
string lo = s;
char first = s[0];
for (int j = 0; j < (int) lo.size(); j++) if (lo[j] == first) lo[j] = '0';
return stoi(hi) - stoi(lo);
}JavaScript
var minMaxDifference = function(num) {
var s = String(num);
var maxS = s;
for (var i = 0; i < s.length; i++) {
if (s.charAt(i) !== "9") {
maxS = s.split(s.charAt(i)).join("9");
break;
}
}
var minS = s.split(s.charAt(0)).join("0");
return parseInt(maxS, 10) - parseInt(minS, 10);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Greedy Algorithms