1881. Maximum Value after Insertion


Problem Description

The problem presents us with two input values: a large integer n represented as a string and an integer digit x which range from 1 to 9. The goal is to insert the digit x into the string representation of n in such a way that the resulting number is maximized. If n is negative, x can be inserted anywhere except before the minus sign.

Here are some key points to keep in mind:

  • We can insert x in between any two digits of n.
  • The challenge is to figure out the most optimal position for x to achieve the largest possible value.
  • The comparison of where to insert x differs based on whether n is negative or positive.

Intuition

The intuition behind the solution stems from understanding how numerical value is affected by the placement of digits. For positive numbers, placing a larger digit towards the left increases the number's value. Thus, for a positive n, we look for the first instance where x is greater than a digit in n, and insert x before this digit to maximize the value.

Conversely, for negative numbers, we want to minimize the value of the negative magnitude to maximize n's value. Therefore, we look for the first digit in n that is smaller than x, and insert x after this digit to ensure the negative number is as small as Ppossible (which makes n as large as possible in the negative domain).

Here’s the step-by-step breakdown of our approach:

  1. If n is positive, iterate through its digits.

    • Find the position where the current digit is smaller than x.
    • Insert x before this digit and return the modified string.
  2. If n is negative, skip the minus sign and iterate through the remaining digits.

    • Find the position where the current digit is larger than x.
    • Insert x after this digit, accounting for the skipped minus sign, and return the modified string.
  3. If no such position is found in the above iterations (all digits of n are either larger than x for positive n, or smaller/equal to x for negative n), insert x at the end of the string.

By following this rule, the solution ensures that n's value is maximized according to the problem's constraints.

Solution Approach

The implementation of the solution follows the intuition previously explained. The algorithm is straightforward and can be summarized into the following steps:

  1. Check the Sign of n:

    • Determine if the number n is negative or positive by checking the first character of the string representation of n.
  2. Positive Case (n is not negative):

    • Loop through each digit in n using a for loop.
    • In every iteration, compare the current digit with the given digit x.
    • If the current digit is found to be less than x, use string slicing to insert x before this digit.
    • Return the modified string immediately.
  3. Negative Case (n is negative):

    • Similar to the positive case, use a for loop but start from the second character (skipping the negative sign).
    • Compare each digit with x.
    • If the current digit is greater than x, insert x before this digit.
    • Use string slicing while keeping in mind the negative sign's position (which is at index 0).
    • Return the modified string immediately.
  4. Appending to the End:

    • If the loop completes without finding a suitable position for insertion (which means x is less or equal to all digits in a positive n, or x is less than or equal to all digits in a negative n after the sign), append x at the end of n.

The algorithm does not use any additional data structures, and it relies solely on the properties of string slicing and built-in comparison operators in Python. The solution pattern is iterative and can be classified as a simple linear search, which finds the insertion point by comparing each digit of n with x.

The Python code handles the insertion and string manipulation tasks using concatenation, which adds the string representation of x to the appropriate slice of n. The solution effectively applies the basic concepts of string manipulation with time complexity O(n) where n represents the number of digits in the input string n.

Example Walkthrough

Let's illustrate the solution approach with a small example where we have the integer n represented as the string "273" and the integer digit x as 4. The goal is to insert 4 into "273" such that the resulting number is as large as possible.

Following the solution steps:

  1. Check the Sign of n:

    • "273" does not start with a minus sign; therefore, the number is positive.
  2. Positive Case (n is not negative):

    • We start iterating through each digit in "273".
    • Compare first digit 2 with x (4).
    • 2 is less than 4, so this is where 4 should be inserted to maximize the number.
    • Use string slicing to insert 4 before 2 to get "4273".
    • Return modified string "4273" as the answer.

The resulting number is "4273", which is the largest number that can be formed by inserting 4 into "273".

Now, let's consider a negative example with n as "-456" and x as 3.

  1. Check the Sign of n:

    • "-456" starts with a minus sign; therefore, the number is negative.
  2. Negative Case (n is negative):

    • Skip the minus sign and start the iteration from the second character.
    • Compare each digit with x (3).
    • 4 is greater than 3, so we continue to the next digit.
    • 5 is also greater than 3, so we continue.
    • 6 is greater than 3, so we could keep going, but since there are no more digits, 3 will be inserted at the end.
    • Use string slicing while keeping in mind the negative sign's position.
    • The final string will be "-4536".

In the negative case, the largest number we can form by adding 3 to "-456" is "-4536". Here 3 is inserted at the end because each digit in "-456" after the minus sign is larger than 3, making "-4536" the best possible outcome.

Python Solution

1class Solution:
2    def maxValue(self, n: str, x: int) -> str:
3        # Check if the number n is positive
4        if n[0] != '-':
5            # Loop through each character in the number
6            for i, char in enumerate(n):
7                # If the current digit is less than x, insert x before it
8                if int(char) < x:
9                    return n[:i] + str(x) + n[i:]
10            # If not inserted, add x to the end of the number
11            return n + str(x)
12        else:
13            # The number n is negative, skip the '-' sign and start from the next digit
14            for i, char in enumerate(n[1:]):
15                # If the current digit is greater than x, insert x before it
16                if int(char) > x:
17                    return n[:i + 1] + str(x) + n[i + 1:]
18            # If x has not been inserted yet, add it to the end of the number
19            return n + str(x)
20

Java Solution

1class Solution {
2    public String maxValue(String n, int x) {
3        // Initialize the index variable i to 0
4        int i = 0;
5
6        // If the first character is not a '-'
7        if (n.charAt(0) != '-') {
8            // Loop through the string until we find a digit less than x
9            for (; i < n.length() && n.charAt(i) - '0' >= x; ++i) {
10                // No body for this for loop as it's just used to find the breakpoint
11            }
12        } else {
13            // If the first character is '-', start with the second character
14            // Loop through the string until we find a digit greater than x
15            for (i = 1; i < n.length() && n.charAt(i) - '0' <= x; ++i) {
16                // No body for this for loop as it's just used to find the breakpoint
17            }
18        }
19      
20        // Concatenate the string parts and the integer x:
21        // 1. Substring from the start to i (the breakpoint)
22        // 2. The integer x, converted to a string
23        // 3. The remaining substring from i to the end of the string
24        return n.substring(0, i) + x + n.substring(i);
25    }
26}
27

C++ Solution

1class Solution {
2public:
3    // Function to insert the digit 'x' into the string 'n' to achieve the highest possible value.
4    string maxValue(string n, int x) {
5        int position = 0; // Initialize the insertion position
6
7        // If the number is positive
8        if (n[0] != '-') {
9            // Iterate over the string until we find a digit less than 'x'
10            for (; position < n.size() && (n[position] - '0') >= x; ++position)
11                ; // The loop body is empty since all work is done in the condition
12        } else { // If the number is negative
13            // Start from position 1 to skip the minus sign
14            for (position = 1; position < n.size() && (n[position] - '0') <= x; ++position)
15                ; // Again, the loop body is empty
16        }
17
18        // Insert 'x' into the found position and construct the new string
19        return n.substr(0, position) + to_string(x) + n.substr(position);
20    }
21};
22

Typescript Solution

1/**
2 * Function to insert the maximum value.
3 * Inserts an integer digit `x` into the string representation of a non-negative integer `n`,
4 * at such a position that the new integer is as large as possible.
5 *
6 * @param {string} n - The string representation of the number into which `x` has to be inserted.
7 * @param {number} x - The integer digit to insert into `n`.
8 * @return {string} - The resulting string after insertion of `x`.
9 */
10function maxValue(n: string, x: number): string {
11    // Convert the string `n` into an array of characters
12    let numberArray: string[] = [...n];
13  
14    // Determine the sign of the number (positive by default)
15    let sign: number = 1;
16  
17    // Starting index for the iteration, adjusted if the number is negative
18    let index: number = 0;
19  
20    // If the first character is a minus sign, update the `sign` and `index`
21    if (numberArray[0] === '-') {
22        sign = -1;
23        index++;
24    }
25  
26    // Find the position to insert `x` by iterating over the characters of `n`
27    // For a positive number, it stops before the first digit smaller than `x`
28    // For a negative number, it stops before the first digit larger than `x`
29    while (index < n.length && (parseInt(numberArray[index]) - x) * sign >= 0) {
30        index++;
31    }
32  
33    // Insert `x` into the correct position in the array of characters
34    numberArray.splice(index, 0, x.toString());
35  
36    // Join the array back into a string and return the result
37    return numberArray.join('');
38}
39
40// The maxValue function can now be called with TypeScript syntax
41// Example usage: let result: string = maxValue('123', 5);
42

Time and Space Complexity

The time complexity of the given code is O(n) where n is the length of the input string. The for-loop iterates over the string characters at most once. In each iteration, it performs constant time operations (comparisons and integer conversions). Therefore, the total time taken is linear with respect to the length of the input string.

The space complexity of the code is O(1) (disregarding the input and the output). The reason is that the code only uses a fixed number of variables (i, c, x), and creating the final string output doesn't count towards additional space since the output is required and does not contribute to the space used by the algorithm itself.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫