2566. Maximum Difference by Remapping a Digit

Description

You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.

Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.

Notes:

When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of d1 in num with d2.
Bob can remap a digit to itself, in which case num does not change.
Bob can remap different digits for obtaining minimum and maximum values respectively.
The resulting number after remapping can contain leading zeroes.

Example 1:

Input: num = 11891
Output: 99009
Explanation: 
To achieve the maximum value, Bob can remap the digit 1 to the digit 9 to yield 99899.
To achieve the minimum value, Bob can remap the digit 1 to the digit 0, yielding 890.
The difference between these two numbers is 99009.

Example 2:

Input: num = 90
Output: 99
Explanation:
The maximum value that can be returned by the function is 99 (if 0 is replaced by 9) and the minimum value that can be returned by the function is 0 (if 9 is replaced by 0).
Thus, we return 99.

Constraints:

1 <= num <= 10⁸

Solutions

Solution 1: Greedy

Thinking

Remap one digit throughout the number to maximize one value and minimize the other, then subtract. Few digits would allow enumerating pairs, but the optimal remaps are unique.

The minimum replaces every copy of the leading digit by \(0\). The maximum replaces every copy of the leftmost non-\(9\) by \(9\). An all-\(9\) number is already maximal.

First, we convert the number to a string \(s\).

To get the minimum value, we just need to find the first digit \(s[0]\) in the string \(s\), and then replace all \(s[0]\) in the string with \(0\).

To get the maximum value, we need to find the first digit \(s[i]\) in the string \(s\) that is not \(9\), and then replace all \(s[i]\) in the string with \(9\).

Finally, return the difference between the maximum and minimum values.

The time complexity is \(O(\log n)\), and the space complexity is \(O(\log n)\). Where \(n\) is the size of the number \(\textit{num}\).

Python3JavaC++GoTypeScriptRustJavaScriptC

class Solution:
    def minMaxDifference(self, num: int) -> int:
        s = str(num)
        mi = int(s.replace(s[0], '0'))
        for c in s:
            if c != '9':
                return int(s.replace(c, '9')) - mi
        return num - mi

class Solution {
    public int minMaxDifference(int num) {
        String s = String.valueOf(num);
        int mi = Integer.parseInt(s.replace(s.charAt(0), '0'));
        for (char c : s.toCharArray()) {
            if (c != '9') {
                return Integer.parseInt(s.replace(c, '9')) - mi;
            }
        }
        return num - mi;
    }
}

class Solution {
public:
    int minMaxDifference(int num) {
        string s = to_string(num);
        string t = s;
        char first = s[0];
        for (char& c : s) {
            if (c == first) {
                c = '0';
            }
        }
        int mi = stoi(s);
        for (int i = 0; i < t.size(); ++i) {
            if (t[i] != '9') {
                char second = t[i];
                for (int j = i; j < t.size(); ++j) {
                    if (t[j] == second) {
                        t[j] = '9';
                    }
                }
                return stoi(t) - mi;
            }
        }
        return num - mi;
    }
};

func minMaxDifference(num int) int {
    s := []byte(strconv.Itoa(num))
    first := s[0]
    for i := range s {
        if s[i] == first {
            s[i] = '0'
        }
    }
    mi, _ := strconv.Atoi(string(s))
    t := []byte(strconv.Itoa(num))
    for i := range t {
        if t[i] != '9' {
            second := t[i]
            for j := i; j < len(t); j++ {
                if t[j] == second {
                    t[j] = '9'
                }
            }
            mx, _ := strconv.Atoi(string(t))
            return mx - mi
        }
    }
    return num - mi
}

function minMaxDifference(num: number): number {
    const s = num.toString();
    const mi = +s.replaceAll(s[0], '0');
    for (const c of s) {
        if (c !== '9') {
            const mx = +s.replaceAll(c, '9');
            return mx - mi;
        }
    }
    return num - mi;
}

impl Solution {
    pub fn min_max_difference(num: i32) -> i32 {
        let s = num.to_string();
        let mi = s.replace(s.chars().next().unwrap(), "0").parse::<i32>().unwrap();
        for c in s.chars() {
            if c != '9' {
                let mx = s.replace(c, "9").parse::<i32>().unwrap();
                return mx - mi;
            }
        }
        num - mi
    }
}

/**
 * @param {number} num
 * @return {number}
 */
var minMaxDifference = function (num) {
    const s = num.toString();
    const mi = +s.replaceAll(s[0], '0');
    for (const c of s) {
        if (c !== '9') {
            const mx = +s.replaceAll(c, '9');
            return mx - mi;
        }
    }
    return num - mi;
};

int minMaxDifference(int num) {
    char s[12];
    sprintf(s, "%d", num);

    int mi;
    {
        char tmp[12];
        char t = s[0];
        for (int i = 0; s[i]; i++) {
            tmp[i] = (s[i] == t) ? '0' : s[i];
        }
        tmp[strlen(s)] = '\0';
        mi = atoi(tmp);
    }

    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c != '9') {
            char tmp[12];
            for (int j = 0; s[j]; j++) {
                tmp[j] = (s[j] == c) ? '9' : s[j];
            }
            tmp[strlen(s)] = '\0';
            return atoi(tmp) - mi;
        }
    }

    return num - mi;
}

2566. Maximum Difference by Remapping a Digit

Description

Solutions

Solution 1: Greedy

Comments