Scale Engineer

Maximum Difference by Remapping a Digit

Easy
#2346Time: O(C * L), where C is the number of possible remappings (10 * 10 = 100) and L is the number of digits in `num`. Since C is a constant, this simplifies to O(L), but with a large constant factor.Space: O(L), where L is the number of digits in `num`. This space is used to store the string representation of the number and the temporary strings created in each iteration.
Patterns
MathGreedy

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach exhaustively tries every possible remapping. There are 10 digits to choose from (0-9) and 10 digits to remap to (0-9). We can iterate through all 100 possible pairs of (digit to replace, replacement digit), apply the remapping to the original number, and keep track of the minimum and maximum values encountered.

Algorithm

  • Convert the input number num to its string representation, s.
  • Initialize maxVal and minVal to num.
  • Iterate through all possible digits to be replaced, d1, from '0' to '9'.
  • Inside this loop, iterate through all possible replacement digits, d2, from '0' to '9'.
  • For each pair (d1, d2), create a new string temp_s by replacing all occurrences of d1 in s with d2.
  • Convert temp_s to an integer currentVal.
  • Update maxVal = max(maxVal, currentVal).
  • Update minVal = min(minVal, currentVal).
  • After the loops complete, return maxVal - minVal.

Walkthrough

The core idea is to simulate the process for all 100 possible remappings. We convert the number to a string to make digit replacement easier. We then use two nested loops: the outer loop selects the digit d1 to be replaced (from '0' to '9'), and the inner loop selects the digit d2 to replace it with (from '0' to '9'). In each iteration, we generate a new number by performing the replacement s.replace(d1, d2). This new number is then compared with our running maximum and minimum values, which are updated accordingly. Finally, after checking all possibilities, the difference between the maximum and minimum gives the answer.

Complexity

Time

O(C * L), where C is the number of possible remappings (10 * 10 = 100) and L is the number of digits in `num`. Since C is a constant, this simplifies to O(L), but with a large constant factor.

Space

O(L), where L is the number of digits in `num`. This space is used to store the string representation of the number and the temporary strings created in each iteration.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Guaranteed to be correct as it explores the entire search space of single-digit remappings.

Cons

  • Performs many redundant or unnecessary computations. For example, it tries remapping digits that are not present in the input number.

  • Less efficient due to a large constant factor (100) in its time complexity compared to a direct analytical approach.

Solutions

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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem