1432: Max Difference You Can Get From Changing an Integer
Problem Statement
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 occurrences of
xin the decimal representation ofnumbyy
Let a and b be the two results from applying the operation to num independently.
Return the max difference between a and b.
Example 1
Input: num = 555
Output: 888
Explanation:
First operation: replace 5 with 9 → 999
Second operation: replace 5 with 1 → 111
Difference: 999 - 111 = 888Example 2
Input: num = 9
Output: 8
Explanation:
First operation: replace 9 with 9 → 9 (no change)
Second operation: replace 9 with 1 → 1
Difference: 9 - 1 = 8Approach 1: Greedy Algorithm
This approach efficiently computes the maximum possible number and minimum possible number through digit replacement operations.
Algorithm Steps
- For maximum number:
- Convert the number to a string
- Find the first non-'9' digit from left to right
- Replace all occurrences of this digit with '9'
- For minimum number:
- If the first digit is not '1', replace it and all its occurrences with '1'
- If the first digit is '1':
- Find the first digit that is not '0' or '1'
- Replace all occurrences of this digit with '0'
- Return the difference between the maximum and minimum numbers
class Solution {
public:
int maxDiff(int num) {
string s = to_string(num);
string s1 = s;
string s2 = s;
char target = s1[0];
int i = 0;
while (i < s1.length() && s1[i] == '9') {
i++;
}
if (i < s1.length()) {
target = s1[i];
while (i < s1.length()) {
if (s1[i] == target) {
s1[i] = '9';
}
i++;
}
}
if (s2[0] != '1') {
target = s2[0];
for (i = 0; i < s2.length(); i++) {
if (s2[i] == target) {
s2[i] = '1';
}
}
} else {
i = 1;
while (i < s2.length() && (s2[i] == '0' || s2[i] == '1')) {
i++;
}
if (i < s2.length()) {
target = s2[i];
for (int j = i; j < s2.length(); j++) {
if (s2[j] == target) {
s2[j] = '0';
}
}
}
}
return stoi(s1) - stoi(s2);
}
};class Solution {
public int maxDiff(int num) {
String s = String.valueOf(num);
char[] arr1 = s.toCharArray();
char[] arr2 = s.toCharArray();
int i = 0;
while (i < arr1.length && arr1[i] == '9') {
i++;
}
if (i < arr1.length) {
char target = arr1[i];
for (int j = i; j < arr1.length; j++) {
if (arr1[j] == target) {
arr1[j] = '9';
}
}
}
if (arr2[0] != '1') {
char target = arr2[0];
for (i = 0; i < arr2.length; i++) {
if (arr2[i] == target) {
arr2[i] = '1';
}
}
} else {
i = 1;
while (i < arr2.length && (arr2[i] == '0' || arr2[i] == '1')) {
i++;
}
if (i < arr2.length) {
char target = arr2[i];
for (int j = i; j < arr2.length; j++) {
if (arr2[j] == target) {
arr2[j] = '0';
}
}
}
}
return Integer.parseInt(new String(arr1)) -
Integer.parseInt(new String(arr2));
}
}class Solution:
def maxDiff(self, num: int) -> int:
s = str(num)
s1 = list(s)
s2 = list(s)
i = 0
while i < len(s1) and s1[i] == '9':
i += 1
if i < len(s1):
target = s1[i]
for j in range(i, len(s1)):
if s1[j] == target:
s1[j] = '9'
if s2[0] != '1':
target = s2[0]
for i in range(len(s2)):
if s2[i] == target:
s2[i] = '1'
else:
i = 1
while i < len(s2) and s2[i] in ['0', '1']:
i += 1
if i < len(s2):
target = s2[i]
for j in range(i, len(s2)):
if s2[j] == target:
s2[j] = '0'
return int("".join(s1)) - int("".join(s2))Approach 2: Optimized Greedy
This approach optimizes the greedy solution by combining max and min calculations and handles edge cases efficiently.
class Solution {
public:
int maxDiff(int num) {
string s = to_string(num);
int n = s.size();
if (n == 1) return 8;
string maxStr = s;
char maxTarget = 0;
for (int i = 0; i < n; i++) {
if (s[i] != '9') {
maxTarget = s[i];
break;
}
}
if (maxTarget) {
for (int i = 0; i < n; i++) {
if (maxStr[i] == maxTarget) {
maxStr[i] = '9';
}
}
}
string minStr = s;
char minTarget = 0;
char replaceWith = '0';
if (s[0] != '1') {
minTarget = s[0];
replaceWith = '1';
} else {
for (int i = 1; i < n; i++) {
if (s[i] != '0' && s[i] != '1') {
minTarget = s[i];
replaceWith = '0';
break;
}
}
}
if (minTarget) {
for (int i = 0; i < n; i++) {
if (minStr[i] == minTarget) {
minStr[i] = replaceWith;
}
}
}
return stoi(maxStr) - stoi(minStr);
}
};class Solution {
public int maxDiff(int num) {
String s = String.valueOf(num);
int n = s.length();
if (n == 1) return 8;
char[] maxArr = s.toCharArray();
char maxTarget = 0;
for (int i = 0; i < n; i++) {
if (maxArr[i] != '9') {
maxTarget = maxArr[i];
break;
}
}
if (maxTarget != 0) {
for (int i = 0; i < n; i++) {
if (maxArr[i] == maxTarget) {
maxArr[i] = '9';
}
}
}
char[] minArr = s.toCharArray();
char minTarget = 0;
char replaceWith = '0';
if (minArr[0] != '1') {
minTarget = minArr[0];
replaceWith = '1';
} else {
for (int i = 1; i < n; i++) {
if (minArr[i] != '0' && minArr[i] != '1') {
minTarget = minArr[i];
replaceWith = '0';
break;
}
}
}
if (minTarget != 0) {
for (int i = 0; i < n; i++) {
if (minArr[i] == minTarget) {
minArr[i] = replaceWith;
}
}
}
return Integer.parseInt(new String(maxArr)) -
Integer.parseInt(new String(minArr));
}
}class Solution:
def maxDiff(self, num: int) -> int:
s = str(num)
n = len(s)
if n == 1:
return 8
max_arr = list(s)
max_target = None
for i in range(n):
if max_arr[i] != '9':
max_target = max_arr[i]
break
if max_target is not None:
for i in range(n):
if max_arr[i] == max_target:
max_arr[i] = '9'
min_arr = list(s)
min_target = None
replace_with = '0'
if min_arr[0] != '1':
min_target = min_arr[0]
replace_with = '1'
else:
for i in range(1, n):
if min_arr[i] != '0' and min_arr[i] != '1':
min_target = min_arr[i]
replace_with = '0'
break
if min_target is not None:
for i in range(n):
if min_arr[i] == min_target:
min_arr[i] = replace_with
return int("".join(max_arr)) - int("".join(min_arr))Approach 3: Brute Force
This approach tries all possible digit replacements to find the maximum and minimum valid numbers.
class Solution {
public:
int maxDiff(int num) {
string s = to_string(num);
int maxVal = INT_MIN;
int minVal = INT_MAX;
for (char x = '0'; x <= '9'; x++) {
for (char y = '0'; y <= '9'; y++) {
string t = s;
for (char &c : t) {
if (c == x) c = y;
}
if (t[0] == '0') continue;
int val = stoi(t);
if (val > maxVal) maxVal = val;
if (val < minVal) minVal = val;
}
}
return maxVal - minVal;
}
};class Solution {
public int maxDiff(int num) {
String s = String.valueOf(num);
int maxVal = Integer.MIN_VALUE;
int minVal = Integer.MAX_VALUE;
for (char x = '0'; x <= '9'; x++) {
for (char y = '0'; y <= '9'; y++) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
if (c == x) sb.append(y);
else sb.append(c);
}
String t = sb.toString();
if (t.charAt(0) == '0') continue;
int val = Integer.parseInt(t);
if (val > maxVal) maxVal = val;
if (val < minVal) minVal = val;
}
}
return maxVal - minVal;
}
}class Solution:
def maxDiff(self, num: int) -> int:
s = str(num)
max_val = -10**9
min_val = 10**9
for x in '0123456789':
for y in '0123456789':
t = s.replace(x, y)
if t[0] == '0':
continue
val = int(t)
if val > max_val:
max_val = val
if val < min_val:
min_val = val
return max_val - min_valApproach Comparison
| Approach | Time | Space | Best For |
|---|---|---|---|
| Greedy | O(n) | O(n) | Most cases |
| Optimized Greedy | O(n) | O(n) | Edge cases |
| Brute Force | O(100n) | O(n) | Small inputs |
Edge Cases
1. Single-digit numbers
Input: 9 → Output: 8 (9 - 1)2. Numbers with all digits same
Input: 111 → Output: 888 (999 - 111)3. Numbers starting with 1
Input: 123 → Output: 820 (923 - 103)4. Numbers with no replaceable digits
Input: 9999 → Output: 0 (no replacements needed)Frequently Asked Questions
Why do we replace the first non-9 digit for the maximum number?
Replacing the leftmost non-9 digit with 9 gives the greatest value increase since digits to the left have higher place values.
How do we handle numbers starting with 1 for minimum value?
When the first digit is 1, we look for the first non-zero/non-one digit and replace it with 0 to minimize the number while avoiding leading zeros.
What about digits that don't appear in the number?
Our algorithm only considers digits that actually appear in the number, so unused digits don't affect the result.
Why does the greedy approach work for this problem?
The greedy approach works because the operations allow us to independently maximize one number and minimize the other through optimal digit replacements.
How do we handle edge cases like single-digit numbers?
For single-digit numbers, the maximum difference is always 8 (9-1). We handle this as a special case in the optimized approach.
Can the difference be negative?
No, the problem asks for the maximum difference which is always non-negative. Our solutions ensure we subtract the smaller number from the larger one.
Why not always replace with 9 for maximum and 0 for minimum?
We must avoid creating leading zeros, which would make the number invalid. Our algorithm carefully handles these constraints.
How does the brute force approach avoid invalid numbers?
The brute force approach explicitly checks for leading zeros and skips these invalid transformations.
What's the space complexity of these solutions?
All solutions use O(n) space where n is the number of digits, primarily for storing the string representation of the number.
Which approach is best for large numbers?
The greedy approach (O(n) time) is optimal for large numbers up to the constraint (10^8), while the brute force approach (O(100n)) is acceptable but less efficient.
Why is the single-digit case handled as 8?
For any single-digit number, we can get 9 (by replacing the digit with 9) and 1 (by replacing with 1), resulting in 9-1=8.
How do we handle numbers like 10?
For 10: Max number is 99 (replace 1 with 9), min number is 10 (no valid replacement that reduces value without creating leading zero), difference 89.