Max Difference You Can Get From Changing an Integer

Max Difference You Can Get From Changing an Integer - Problem

Math Greedy Medium

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 maximum difference between a and b.

Note that neither a nor b may have any leading zeros, and must not be 0.

Input & Output

Example 1 — Basic Case

$ Input: num = 555

› Output: 888

💡 Note: To maximize: all digits are 5 (not 9), so replace 5→9 to get 999. To minimize: first digit is 5≠1, so replace 5→1 to get 111. Difference: 999 - 111 = 888

Example 2 — First Digit is 9

$ Input: num = 901

› Output: 888

💡 Note: To maximize: first digit is 9, second digit is 0 (not 9), so replace 0→9 to get 991. To minimize: first digit 9≠1, so replace 9→1 to get 101. Difference: 991 - 101 = 890

Example 3 — Edge Case with 1

$ Input: num = 123

› Output: 820

💡 Note: To maximize: first digit 1 (not 9), so replace 1→9 to get 923. To minimize: first digit 1≠1 is false, so find next non-0/1 digit which is 2, replace 2→0 to get 103. Difference: 923 - 103 = 820

Constraints

1 ≤ num ≤ 10⁸
num does not contain any leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

Original number with specific digit pattern

Transform

Apply optimal digit replacement strategy

Output

Calculate maximum possible difference

Key Takeaway

🎯 Key Insight: The leftmost digit has the highest impact, so prioritize changing it for maximum effect

Asked in

G Google 35 M Microsoft 28 a Amazon 22

The key insight is that leftmost digits have the highest impact on a number's value. For maximum value, find the first non-9 digit and replace it with 9. For minimum value, if the first digit is not 1, replace it with 1; otherwise find the first digit that's not 0 or 1 and replace it with 0. Best approach is greedy strategy. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n)	O(n)	Strategically choose optimal digit replacements for maximum and minimum values
Brute Force	O(1)	O(1)	Try all possible digit replacements and find maximum difference

Greedy Approach — Algorithm Steps

For maximum: scan left to right, find first non-9 digit, replace all occurrences with 9
For minimum: if first digit > 1, replace with 1; else find first digit that's not 0 or 1, replace with 0
Calculate difference between maximum and minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Maximize Strategy

Find leftmost non-9 digit and replace with 9

Minimize Strategy

Replace first digit with 1, or find first non-0/1 and replace with 0

Calculate Difference

Return max - min

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int num) {
    char numStr[20];
    sprintf(numStr, "%d", num);
    int len = strlen(numStr);
    
    // Find maximum value
    char maxStr[20];
    strcpy(maxStr, numStr);
    for (int i = 0; i < len; i++) {
        if (numStr[i] != '9') {
            for (int j = 0; j < len; j++) {
                if (maxStr[j] == numStr[i]) {
                    maxStr[j] = '9';
                }
            }
            break;
        }
    }
    
    // Find minimum value
    char minStr[20];
    strcpy(minStr, numStr);
    if (numStr[0] != '1') {
        // Replace first digit with 1
        char firstDigit = numStr[0];
        for (int j = 0; j < len; j++) {
            if (minStr[j] == firstDigit) {
                minStr[j] = '1';
            }
        }
    } else {
        // First digit is 1, find first digit that's not 0 or 1
        for (int i = 1; i < len; i++) {
            if (numStr[i] != '0' && numStr[i] != '1') {
                char targetDigit = numStr[i];
                for (int j = 0; j < len; j++) {
                    if (minStr[j] == targetDigit) {
                        minStr[j] = '0';
                    }
                }
                break;
            }
        }
    }
    
    return atoi(maxStr) - atoi(minStr);
}

int main() {
    int num;
    scanf("%d", &num);
    
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the digit string, where n is number of digits

✓ Linear Growth

Space Complexity

O(n)

String manipulation requires O(n) space for digit representation

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler