Maximum Difference by Remapping a Digit - Practice Coding Problems

Maximum Difference by Remapping a Digit - Problem

Math Greedy Easy

You are given an integer num. You know that Bob will sneakily remap one of the 10 possible digits (0 to 9) to another digit.

Return the difference between the maximum and minimum values Bob can make by remapping exactly one digit in num.

Notes:

When Bob remaps a digit d1 to another digit d2, Bob replaces all occurrences of d1 in num with d2.
Bob can remap a digit to itself, in which case num does not change.
Bob can remap different digits for obtaining minimum and maximum values respectively.
The resulting number after remapping can contain leading zeroes.

Input & Output

Example 1 — Basic Case

$ Input: num = 123

› Output: 900

💡 Note: For maximum: replace 1→9 to get 923. For minimum: replace 1→0 to get 023 (which is 23). Difference is 923 - 23 = 900.

Example 2 — All Same Digits

$ Input: num = 555

› Output: 888

💡 Note: For maximum: replace 5→9 to get 999. For minimum: replace 5→1 to get 111. Difference is 999 - 111 = 888.

Example 3 — Already Has 9

$ Input: num = 9321

› Output: 8019

💡 Note: For maximum: replace 3→9 to get 9921. For minimum: replace 9→1 to get 1321. Difference is 9921 - 1321 = 8600.

Constraints

1 ≤ num ≤ 10⁸

Visualization

Tap to expand

Understanding the Visualization

Input

Given number that can have one digit remapped

Process

Find optimal digit replacements for max and min values

Output

Return difference between maximum and minimum possible values

Key Takeaway

🎯 Key Insight: Prioritize changing leftmost digits since they have the greatest impact on the number's value

Asked in

G Google 15 M Microsoft 12 A Amazon 8

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

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Digit Replacements	O(1)	O(1)	Try replacing every digit with every other digit and track min/max values
Greedy - Smart Digit Selection	O(n)	O(1)	Strategically choose digits to replace for maximum impact

Brute Force - Try All Digit Replacements — Algorithm Steps

Step 1: Convert number to string for easy digit manipulation
Step 2: Try replacing each digit (0-9) with each other digit (0-9)
Step 3: Convert back to integer and track min/max values
Step 4: Return difference between max and min

Visualization

Tap to expand

Step-by-Step Walkthrough

Input

Convert number to string for manipulation

Try All

Test every digit replacement (0→0, 0→1, ..., 9→9)

Track Min/Max

Keep track of smallest and largest values found

Code -

solution.c — C

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

int solution(int num) {
    char s[20];
    sprintf(s, "%d", num);
    int len = strlen(s);
    int minVal = INT_MAX;
    int maxVal = INT_MIN;
    
    // Try replacing each digit (0-9) with each other digit (0-9)
    for (char oldDigit = '0'; oldDigit <= '9'; oldDigit++) {
        for (char newDigit = '0'; newDigit <= '9'; newDigit++) {
            char newS[20];
            strcpy(newS, s);
            for (int i = 0; i < len; i++) {
                if (newS[i] == oldDigit) {
                    newS[i] = newDigit;
                }
            }
            int newVal = atoi(newS);
            if (newVal < minVal) minVal = newVal;
            if (newVal > maxVal) maxVal = newVal;
        }
    }
    
    return maxVal - minVal;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(1)

Always performs exactly 100 operations regardless of input size

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables to store string and track min/max

✓ Linear Space

18.5K Views

Medium Frequency

~15 min Avg. Time

542 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

Brute Force - Try All Digit Replacements — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler