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

Remove Digit From Number to Maximize Result

Number: 2337

Difficulty: Easy

Paid? No

Companies: Amazon, Microsoft, Google

Problem Description

Given a string that represents a positive integer and a digit, remove exactly one occurrence of the digit from the number such that the resulting number (interpreted in decimal) is maximized. The digit is guaranteed to occur at least once in the number.

Key Insights

  • The task is to remove one occurrence of the specified digit from the string.
  • Removing different occurrences will yield different candidate numbers.
  • Since all candidate numbers will have the same length, lexicographic comparison of strings is equivalent to numeric comparison.
  • The simple enumeration approach iterating over every occurrence is efficient given the small constraint (length ≤ 100).

Space and Time Complexity

Time Complexity: O(n^2) in worst-case scenarios due to substring operations when removing a digit from the string (with n being the length of the number).
Space Complexity: O(n) for storing candidate substrings.

Solution

The solution involves iterating over the number string and for every index where the digit to be removed occurs, create a candidate string by omitting that character. Then, compare each candidate with the current maximum to find the candidate that yields the maximum numeric value.
Data structures used include the string for input and temporary strings for each candidate solution. The algorithm is based on enumeration combined with greedy selection of the candidate with the largest value.

Code Solutions

# Function to remove one occurrence of digit to maximize the result
def remove_digit(number: str, digit: str) -> str:
    max_candidate = "0"  # Initialize with a low candidate value as string
    # Iterate over every index in the number string
    for i in range(len(number)):
        # Check if the current character matches the digit to remove
        if number[i] == digit:
            # Create candidate by omitting the digit at index i
            candidate = number[:i] + number[i+1:]
            # Update max_candidate if the current candidate is greater
            if candidate > max_candidate:
                max_candidate = candidate
    return max_candidate

# Example usage:
print(remove_digit("1231", "1"))  # Expected output: "231"
← Back to All Questions