Description
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). Note y can be equal to x.
- Replace all the occurrences of
x in the decimal representation of num by y.
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 = 888
Example 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:
Solutions
Solution 1: Greedy
To obtain the maximum difference, we should take the maximum and minimum values, as this yields the largest difference.
Therefore, we first enumerate each digit in nums from high to low. If a digit is not 9, we replace all occurrences of that digit with 9 to obtain the maximum integer a.
Next, we enumerate each digit in nums from high to low again. The first digit cannot be 0, so if the first digit is not 1, we replace it with 1; for non-leading digits that are different from the first digit, we replace them with 0 to obtain the minimum integer b.
The answer is the difference a - b.
The time complexity is O(log num), and the space complexity is O(log num), where nums is the given integer.
PythonJavaC++GoTypeScriptRust
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)(code-box)
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);
}
}(code-box)
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);
}
};(code-box)
func maxDiff(num int) int {
a, b := num, num
s := strconv.Itoa(num)
for i := range s {
if s[i] != '9' {
a, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "9"))
break
}
}
if s[0] > '1' {
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[0]), "1"))
} else {
for i := 1; i < len(s); i++ {
if s[i] != '0' && s[i] != '1' {
b, _ = strconv.Atoi(strings.ReplaceAll(s, string(s[i]), "0"))
break
}
}
}
return a - b
}(code-box)
function maxDiff(num: number): number {
let a = num.toString();
let b = a;
for (let i = 0; i < a.length; ++i) {
if (a[i] !== '9') {
a = a.split(a[i]).join('9');
break;
}
}
if (b[0] !== '1') {
b = b.split(b[0]).join('1');
} else {
for (let i = 1; i < b.length; ++i) {
if (b[i] !== '0' && b[i] !== '1') {
b = b.split(b[i]).join('0');
break;
}
}
}
return +a - +b;
}(code-box)
impl Solution {
pub fn max_diff(num: i32) -> i32 {
let a = num.to_string();
let mut a = a.clone();
let mut b = a.clone();
for c in a.chars() {
if c != '9' {
a = a.replace(c, "9");
break;
}
}
let chars: Vec<char> = b.chars().collect();
if chars[0] != '1' {
b = b.replace(chars[0], "1");
} else {
for &c in &chars[1..] {
if c != '0' && c != '1' {
b = b.replace(c, "0");
break;
}
}
}
a.parse::<i32>().unwrap() - b.parse::<i32>().unwrap()
}
}(code-box)
