Skip to content

1432. Max Difference You Can Get From Changing an Integer

SourceBiweekly Contest 25 Q2DifficultyMediumRating1426

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 <= 108

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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()
    }
}

Comments