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.

Examples

Example 1

1
2
3
4
5

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

1
2
3
4
5

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 <= 10^8

Solution

Method 1 – Greedy Digit Replacement

Intuition

To maximize the difference, we want to create the largest and smallest possible numbers by replacing digits. For the maximum, replace the first non-9 digit with 9 everywhere. For the minimum, replace the first digit (if not 1) with 1, or the first non-0/1 digit with 0, ensuring no leading zeros.

Approach

  1. Convert the number to a string for easy digit manipulation.
  2. For the maximum value:
  • Find the first digit that is not 9.
  • Replace all its occurrences with 9.
  1. For the minimum value:
  • If the first digit is not 1, replace all its occurrences with 1.
  • Otherwise, find the first digit (after the first) that is not 0 or 1, and replace all its occurrences with 0.
  • Ensure the result does not have leading zeros.
  1. Convert both results back to integers and return their difference.

Code

 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

class Solution {
public:
   int maxDiff(int num) {
      string s = to_string(num);
      string mx = s, mn = s;
      // Maximize: replace first non-9 digit with 9
      for (char c : s) {
        if (c != '9') {
           for (char &d : mx)
              if (d == c) d = '9';
           break;
        }
      }
      // Minimize: replace first digit if not 1, else first non-0/1 digit with 0
      if (s[0] != '1') {
        char t = s[0];
        for (char &d : mn)
           if (d == t) d = '1';
      } else {
        for (int i = 1; i < s.size(); ++i) {
           if (s[i] != '0' && s[i] != '1') {
              char t = s[i];
              for (char &d : mn)
                if (d == t) d = '0';
              break;
           }
        }
      }
      int a = stoi(mx), b = stoi(mn);
      return a - b;
   }
};
 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
37
38
39
40
41
42

func maxDiff(num int) int {
   s := []byte(fmt.Sprintf("%d", num))
   mx := make([]byte, len(s))
   mn := make([]byte, len(s))
   copy(mx, s)
   copy(mn, s)
   // Maximize
   for _, c := range s {
      if c != '9' {
        for i := range mx {
           if mx[i] == c {
              mx[i] = '9'
           }
        }
        break
      }
   }
   // Minimize
   if s[0] != '1' {
      t := s[0]
      for i := range mn {
        if mn[i] == t {
           mn[i] = '1'
        }
      }
   } else {
      for i := 1; i < len(s); i++ {
        if s[i] != '0' && s[i] != '1' {
           t := s[i]
           for j := range mn {
              if mn[j] == t {
                mn[j] = '0'
              }
           }
           break
        }
      }
   }
   a, _ := strconv.Atoi(string(mx))
   b, _ := strconv.Atoi(string(mn))
   return a - b
}
 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

class Solution {
   public int maxDiff(int num) {
      String s = Integer.toString(num);
      char[] mx = s.toCharArray();
      char[] mn = s.toCharArray();
      // Maximize
      for (char c : mx) {
        if (c != '9') {
           for (int i = 0; i < mx.length; i++)
              if (mx[i] == c) mx[i] = '9';
           break;
        }
      }
      // Minimize
      if (mn[0] != '1') {
        char t = mn[0];
        for (int i = 0; i < mn.length; i++)
           if (mn[i] == t) mn[i] = '1';
      } else {
        for (int i = 1; i < mn.length; i++) {
           if (mn[i] != '0' && mn[i] != '1') {
              char t = mn[i];
              for (int j = 0; j < mn.length; j++)
                if (mn[j] == t) mn[j] = '0';
              break;
           }
        }
      }
      int a = Integer.parseInt(new String(mx));
      int b = Integer.parseInt(new String(mn));
      return a - b;
   }
}
 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

class Solution {
   fun maxDiff(num: Int): Int {
      val s = num.toString()
      val mx = s.toCharArray()
      val mn = s.toCharArray()
      // Maximize
      for (c in mx) {
        if (c != '9') {
           for (i in mx.indices)
              if (mx[i] == c) mx[i] = '9'
           break
        }
      }
      // Minimize
      if (mn[0] != '1') {
        val t = mn[0]
        for (i in mn.indices)
           if (mn[i] == t) mn[i] = '1'
      } else {
        for (i in 1 until mn.size) {
           if (mn[i] != '0' && mn[i] != '1') {
              val t = mn[i]
              for (j in mn.indices)
                if (mn[j] == t) mn[j] = '0'
              break
           }
        }
      }
      val a = String(mx).toInt()
      val b = String(mn).toInt()
      return a - b
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
   def maxDiff(self, num: int) -> int:
      s = str(num)
      mx = list(s)
      mn = list(s)
      # Maximize
      for c in s:
        if c != '9':
           mx = [ '9' if d == c else d for d in mx ]
           break
      # Minimize
      if s[0] != '1':
        t = s[0]
        mn = [ '1' if d == t else d for d in mn ]
      else:
        for i in range(1, len(s)):
           if s[i] != '0' and s[i] != '1':
              t = s[i]
              mn = [ '0' if d == t else d for d in mn ]
              break
      a = int(''.join(mx))
      b = int(''.join(mn))
      return a - b
 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

impl Solution {
   pub fn max_diff(num: i32) -> i32 {
      let s = num.to_string();
      let mut mx = s.clone().into_bytes();
      let mut mn = s.clone().into_bytes();
      // Maximize
      for &c in s.as_bytes() {
        if c != b'9' {
           for d in mx.iter_mut() {
              if *d == c { *d = b'9'; }
           }
           break;
        }
      }
      // Minimize
      if s.as_bytes()[0] != b'1' {
        let t = s.as_bytes()[0];
        for d in mn.iter_mut() {
           if *d == t { *d = b'1'; }
        }
      } else {
        for i in 1..s.len() {
           let c = s.as_bytes()[i];
           if c != b'0' && c != b'1' {
              for d in mn.iter_mut() {
                if *d == c { *d = b'0'; }
              }
              break;
           }
        }
      }
      let a = String::from_utf8(mx).unwrap().parse::<i32>().unwrap();
      let b = String::from_utf8(mn).unwrap().parse::<i32>().unwrap();
      a - b
   }
}

Complexity

  • ⏰ Time complexity: O(n) where n is the number of digits in num.
  • 🧺 Space complexity: O(n) for storing digit arrays.