1432. Max Difference You Can Get From Changing an Integer

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:

1 <= num <= 10⁸

Solutions

Solution 1: Greedy

Thinking

\(num\le 10^8\), so there are few digits. One replacement rewrites every occurrence of a digit; the maximum difference is max-value minus min-value after one replacement each.

For the maximum, replace the first non-\(9\) digit with \(9\) everywhere. For the minimum, replace the leading digit with \(1\) if it is not already \(1\); otherwise replace a later digit that is not \(0\) or \(1\) with \(0\), avoiding a leading zero.

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 \(\textit{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 \(\textit{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 \textit{num})\), and the space complexity is \(O(\log \textit{num})\), where \(\textit{nums}\) is the given integer.

Python3JavaC++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)

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);
    }
};

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
}

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;
}

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()
    }
}

1432. Max Difference You Can Get From Changing an Integer

Description

Solutions

Solution 1: Greedy

Comments