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
innum
withd2
. - 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 <= 108
Solutions
Solution 1: Greedy
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 $num$.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
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 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
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 32 33 34 35 36 |
|
Solution 2
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 |
|