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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Value after Insertion

Number: 2011

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a string representation of an integer n (which can be negative) and a digit x (in the range [1,9]), insert x into n such that the resulting integer is maximized. For a positive n, inserting x at the optimal position will make n as big as possible, while for a negative n, you want to reduce the absolute value by placing x in an optimal spot. Note that for a negative number, you cannot place x before the '-' sign.

Key Insights

  • For a positive number, the goal is to create the largest number by inserting x before the first digit that is smaller than x.
  • For a negative number, since the value is reversed, insert x before the first digit that is greater than x to minimize the absolute value.
  • The problem can be solved using a single pass (greedy algorithm) through the string representation of n.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the number string, as we traverse the string once. Space Complexity: O(n), for constructing the new string with the inserted digit.

Solution

We first check if the number n is positive or negative. For a positive n, we iterate through its digits and look for the first digit that is less than x; inserting x at this location yields a larger number. If no such digit is found, x is appended at the end. For a negative n, we skip the '-' and then look for the first digit that is greater than x; inserting x here minimizes the number's absolute value, thus maximizing it. The solution uses a greedy approach with simple string manipulation.

Code Solutions

# Python solution for Maximum Value after Insertion

def maximumValueAfterInsertion(n: str, x: int) -> str:
    x_char = str(x)
    
    # Handle positive numbers
    if n[0] != '-':
        for i in range(len(n)):
            # Find first digit less than x to insert
            if n[i] < x_char:
                # Insert x_char at index i and return the result
                return n[:i] + x_char + n[i:]
        # If x is not inserted in the loop, append it at the end
        return n + x_char
    else:
        # For negative numbers, start from index 1 to skip the minus sign
        for i in range(1, len(n)):
            # Find first digit greater than x to insert
            if n[i] > x_char:
                return n[:i] + x_char + n[i:]
        # If not inserted, append x_char at the end
        return n + x_char

# Example usage:
print(maximumValueAfterInsertion("73", 6))   # Expected output: "763"
print(maximumValueAfterInsertion("-55", 2))  # Expected output: "-255"
← Back to All Questions