Scale Engineer

Max Difference You Can Get From Changing an Integer

Med
#1325Time: O(d), where `d` is the number of digits in `num`. The two loops for `x` and `y` run a constant 100 times. String operations inside the loop take O(d) time.Space: O(d) to store the string representation of the number and its transformations, where `d` is the number of digits in `num`.2 companies
Patterns
MathGreedy
Companies
TrexquantMercari

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach explores all possible transformations of the number num. A transformation is defined by choosing a digit x (0-9) to be replaced and a digit y (0-9) to replace it with. We generate all possible valid numbers by trying every pair of (x, y) and find the maximum and minimum among them.

Algorithm

  • Initialize max_val and min_val with the input num.
  • Convert num to its string representation, s.
  • Loop through x from '0' to '9' (digit to be replaced).
  • Inside, loop through y from '0' to '9' (replacement digit).
  • Apply the replacement to get newS.
  • Check if newS is a valid number (no leading zeros, not zero).
  • If valid, parse it to an integer current_val.
  • Update max_val = Math.max(max_val, current_val).
  • Update min_val = Math.min(min_val, current_val).
  • Return max_val - min_val.

Walkthrough

This approach systematically tries every possible transformation to find the maximum and minimum possible outcomes. A transformation is defined by picking a digit x (from 0 to 9) and a replacement digit y (from 0 to 9).

The algorithm iterates through all 100 possible (x, y) pairs. For each pair, it applies the transformation to the original number num. It keeps track of the maximum and minimum valid numbers generated throughout this process. A generated number is valid if it does not have a leading zero (unless it is the number 0 itself, which is not possible here as num >= 1 and results must not be 0).

The final result is the difference between the overall maximum and minimum values found, which corresponds to max(a) - min(b).

public int maxDiff(int num) {    String s = Integer.toString(num);    int maxVal = num;    int minVal = num;     for (char x = '0'; x <= '9'; x++) {        for (char y = '0'; y <= '9'; y++) {            String newS = s.replace(x, y);                        // Check for invalid leading zeros            if (newS.charAt(0) == '0' && newS.length() > 1) {                continue;            }                        int currentVal = Integer.parseInt(newS);            // The problem states the result must not be 0            if (currentVal == 0) {                continue;            }             maxVal = Math.max(maxVal, currentVal);            minVal = Math.min(minVal, currentVal);        }    }    return maxVal - minVal;}

Complexity

Time

O(d), where `d` is the number of digits in `num`. The two loops for `x` and `y` run a constant 100 times. String operations inside the loop take O(d) time.

Space

O(d) to store the string representation of the number and its transformations, where `d` is the number of digits in `num`.

Trade-offs

Pros

  • Simple to understand and implement.

  • Guaranteed to be correct as it checks all possibilities.

Cons

  • Performs many redundant and unnecessary computations.

  • Less efficient due to a large constant factor (100) compared to a targeted approach.

Solutions

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

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