# Max Difference You Can Get From Changing an Integer
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/max-difference-you-can-get-from-changing-an-integer)
Canonical: https://scaleengineer.com/dsa/problems/max-difference-you-can-get-from-changing-an-integer
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Companies:** [Trexquant](https://scaleengineer.com/companies/trexquant), [Mercari](https://scaleengineer.com/companies/mercari)
---
## Problem
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
## Brute Force Enumeration
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.
**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`.
**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.
### Explanation
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)`.

```java
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;
}
```
### 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`.

## Greedy Approach
To maximize the difference `a - b`, we can maximize `a` and minimize `b` independently using a greedy strategy. This involves making the most impactful change at the most significant digit possible for both maximization and minimization, while respecting the problem's constraints.
**Time:** O(d), where `d` is the number of digits in `num`. The solution involves a few linear scans of the number's string representation. · **Space:** O(d), where `d` is the number of digits in `num`. This is for storing the string representation of the number.
**Pros:** Very efficient, as it directly constructs the optimal numbers `a` and `b`.; Avoids unnecessary computations by using a targeted, logical approach.
**Cons:** The logic is more complex and requires careful handling of multiple cases and edge conditions (e.g., leading '1's, all '9's).
### Explanation
This approach directly constructs the optimal numbers `a` and `b` to maximize their difference.

### Finding the Maximum Value `a`
To get the maximum possible number, we want to make the most significant change possible. This means changing a digit to `9`. The largest increase is achieved by changing the leftmost possible digit. So, we find the first digit from the left that is not `9`. Let's call this digit `x`. We then replace all occurrences of `x` with `9`. If all digits are already `9`, no change can increase the number, so `a` is just the original number.

### Finding the Minimum Value `b`
To get the minimum possible number, we want to make the most significant change downwards. The target replacement digits are `1` (for the leading digit) or `0` (for other digits).
- **Case 1: The first digit is not '1'.** We can achieve the biggest decrease by changing this most significant digit to '1'. So, we take the first digit `x` and replace all its occurrences with '1'.
- **Case 2: The first digit is '1'.** We cannot change it to '0' because that would create an invalid number with a leading zero. So, we must keep the leading '1'. We then scan the rest of the digits from left to right to find the first digit that is not '0' or '1'. Let this digit be `y`. We can replace all occurrences of `y` with '0' to get the minimum number. If all subsequent digits are '0's or '1's, no change can make the number smaller, so `b` is the original number.

```java
class Solution {
    public int maxDiff(int num) {
        String s = Integer.toString(num);
        int a = getMax(s);
        int b = getMin(s);
        return a - b;
    }

    private int getMax(String s) {
        char x = ' ';
        // Find the first digit that is not '9'
        for (char c : s.toCharArray()) {
            if (c != '9') {
                x = c;
                break;
            }
        }
        // If all digits are '9', no change is needed
        if (x == ' ') {
            return Integer.parseInt(s);
        }
        // Replace all occurrences of x with '9'
        String newS = s.replace(x, '9');
        return Integer.parseInt(newS);
    }

    private int getMin(String s) {
        char firstDigit = s.charAt(0);
        // Case 1: First digit is not '1'
        if (firstDigit != '1') {
            String newS = s.replace(firstDigit, '1');
            return Integer.parseInt(newS);
        } else { // Case 2: First digit is '1'
            char y = ' ';
            // Find the first digit after the first that is not '0' or '1'
            for (int i = 1; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c != '0' && c != '1') {
                    y = c;
                    break;
                }
            }
            // If no such digit is found, no change is needed
            if (y == ' ') {
                return Integer.parseInt(s);
            }
            // Replace all occurrences of y with '0'
            String newS = s.replace(y, '0');
            return Integer.parseInt(newS);
        }
    }
}
```
### Algorithm
- To find the maximum value `a`:
  - Find the first digit from the left that is not '9'.
  - Replace all occurrences of this digit with '9'.
  - If all digits are '9', `a` is the original number.
- To find the minimum value `b`:
  - If the first digit is not '1', replace all its occurrences with '1'.
  - If the first digit is '1', find the first subsequent digit that is not '0' or '1'.
  - Replace all occurrences of this digit with '0'.
  - If no such digit exists in the second case, `b` is the original number.
- Calculate `a` and `b` using these rules and return `a - b`.

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
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)

```