We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Value after Insertion

Difficulty: Medium

Problem Description

You are given a very large integer n, represented as a string, and an integer digit x. The digits in n and the digit x are in the inclusive range [1, 9], and n may represent a negative number. You want to maximize n's numerical value by inserting x anywhere in the decimal representation of n. You cannot insert x to the left of the negative sign. Return a string representing the maximum value of n after the insertion.

Key Insights

  • The number n can be positive or negative, which influences where to insert x.
  • For positive n, x should be inserted before the first digit that is less than x to maximize the number.
  • For negative n, x should be inserted before the first digit that is greater than x to minimize the impact of the negative sign.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string n. Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

The solution involves iterating through the digits of the string representation of n. We check whether n is negative or positive.

  • For positive n, we look for the first digit that is less than x and insert x before it.
  • For negative n, we look for the first digit that is greater than x and insert x before it.
  • If we reach the end of the string without finding a suitable position, we simply append x at the end.

This greedy approach ensures that we maximize the numerical value of n after the insertion.

Code Solutions

def insertDigit(n: str, x: int) -> str:
    # Check if the number is negative
    if n[0] == '-':
        # We are dealing with a negative number
        for i in range(1, len(n)):
            if int(n[i]) > x:
                return n[:i] + str(x) + n[i:]
        return n + str(x)  # Append x if no insertion point found
    else:
        # We are dealing with a positive number
        for i in range(len(n)):
            if int(n[i]) < x:
                return n[:i] + str(x) + n[i:]
        return n + str(x)  # Append x if no insertion point found

# Example usage
print(insertDigit("99", 9))  # Output: "999"
print(insertDigit("-13", 2))  # Output: "-123"
← Back to All Questions