Max Difference You Can Get From Changing an Integer
Problem
You're given an integer num. Twice, pick a digit x and a digit y (0–9) and replace every occurrence of x in num with y. The result must not have leading zero or be zero. Return the maximum possible difference between the two results.
num = 555888def max_diff(num):
s = str(num)
# max: find first digit != 9 and replace with 9
a = s
for c in s:
if c != '9':
a = s.replace(c, '9'); break
# min: leading digit handled specially
if s[0] != '1':
b = s.replace(s[0], '1')
else:
b = s
for c in s[1:]:
if c not in ('0', '1'):
b = s.replace(c, '0'); break
return int(a) - int(b)function maxDiff(num) {
const s = String(num);
let a = s;
for (const c of s) {
if (c !== '9') { a = s.split(c).join('9'); break; }
}
let b = s;
if (s[0] !== '1') {
b = s.split(s[0]).join('1');
} else {
for (let i = 1; i < s.length; i++) {
if (s[i] !== '0' && s[i] !== '1') { b = s.split(s[i]).join('0'); break; }
}
}
return parseInt(a, 10) - parseInt(b, 10);
}class Solution {
public int maxDiff(int num) {
String s = String.valueOf(num);
String a = s;
for (char c : s.toCharArray()) {
if (c != '9') { a = s.replace(c, '9'); break; }
}
String b = s;
if (s.charAt(0) != '1') {
b = s.replace(s.charAt(0), '1');
} else {
for (int i = 1; i < s.length(); i++) {
char c = s.charAt(i);
if (c != '0' && c != '1') { b = s.replace(c, '0'); break; }
}
}
return Integer.parseInt(a) - Integer.parseInt(b);
}
}int maxDiff(int num) {
string s = to_string(num);
string a = s;
for (char c : s) {
if (c != '9') { replace(a.begin(), a.end(), c, '9'); break; }
}
string b = s;
if (s[0] != '1') {
replace(b.begin(), b.end(), s[0], '1');
} else {
for (int i = 1; i < (int)s.size(); i++) {
if (s[i] != '0' && s[i] != '1') { replace(b.begin(), b.end(), s[i], '0'); break; }
}
}
return stoi(a) - stoi(b);
}Explanation
To make the difference as big as possible we build the largest number we can and the smallest number we can, then subtract. Each is found with a simple greedy rule on the digits.
For the max value a, we scan left to right and find the first digit that is not 9. Replacing every copy of that digit with 9 raises the most significant possible position, giving the biggest result.
For the min value b, the leading digit matters because of the no-leading-zero rule. If the first digit is not 1, we replace every copy of it with 1 (we cannot use 0 up front). If the first digit is already 1, we instead find the first later digit that is not 0 or 1 and turn every copy of it into 0.
Example: num = 555. Max replaces all 5 with 9 giving 999. Min replaces all 5 with 1 (first digit isn't 1) giving 111. The answer is 999 - 111 = 888.
Because each replacement hits the highest-value digit first and we only ever touch the digits once, the two extremes are correct and the subtraction gives the maximum difference.