Maximum by Single Digit Replacement

Find the maximum possible value of integer M by replacing exactly one digit in M with any digit from integer N

Understand the Problem

Problem Statement

Two integers M and N are passed as the input to the program. The program must print the maximum value of M obtained by replacing exactly one digit in M by a digit from N.

Constraints

1 <= Number of digits in M <= 100
1 <= Number of digits in N <= 10
M and N are positive integers
All digits in N are valid candidates for replacement

Examples

Example 1

Input

56120 21

Output

Explanation

The maximum digit from N (21) is 2. We scan M (56120) from left to right. The first digit smaller than 2 is '1' at position 2. Replacing it with 2 gives 56220. Any other replacement would yield a smaller value.

Example 2

Input

895496223 5

Output

895596223

Explanation

The maximum digit from N (5) is 5. We scan M (895496223) from left to right. The first digit smaller than 5 is '4' at position 3. Replacing it with 5 gives 895596223.

Solution

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

int main() {
    char M[101], N[11];
    scanf("%s %s", M, N);
    
    // Find the maximum digit in N
    char maxDigit = '0';
    for (int i = 0; N[i] != '\0'; i++) {
        if (N[i] > maxDigit) {
            maxDigit = N[i];
        }
    }
    
    // Replace the first smaller digit in M
    for (int i = 0; M[i] != '\0'; i++) {
        if (M[i] < maxDigit) {
            M[i] = maxDigit;
            break;
        }
    }
    
    printf("%s\n", M);
    return 0;
}

Time:O(len(M) + len(N)) where len(M) and len(N) are the number of digits

Space:O(1) - only using a few extra variables

Approach:

1. Read both integers as strings to handle large numbers
2. Find the maximum digit in N by iterating through each character
3. Scan through M from left to right and replace the first digit that is smaller than the maximum digit from N
4. Print the modified string M
5. The algorithm stops after the first replacement since we can only make one replacement

Visual Explanation

Loading diagram...

All Problems