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

Minimum Operations to Make a Special Number

Number: 3046

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given a non-negative integer in the form of a string, you are allowed to delete any digit (each deletion counts as one operation). Your goal is to perform the minimum number of deletions so that the resulting number (which can be interpreted as 0 if all digits are removed) is a special number, where a special number is one that is divisible by 25 (i.e. its last two digits are one of "00", "25", "50", or "75").

Key Insights

  • A number is divisible by 25 if and only if its last two digits are any of "00", "25", "50", or "75".
  • Work from the right side of the string to find the required pair of digits while preserving their relative order.
  • For each potential ending pair, count the number of deletions needed: deletions after the last digit candidate and deletions between the two digit candidates.
  • Iterate through all four candidate pairs to find the minimum deletion count needed.

Space and Time Complexity

Time Complexity: O(n) per candidate, and since there are 4 fixed candidates, overall time is O(n).
Space Complexity: O(1) extra space.

Solution

We solve the problem by checking all possible valid endings ("00", "25", "50", "75"). For each candidate ending:

  1. Traverse the input string from right to left to find the digit that should be at the unit place.
  2. Continue the reverse traversal to find the digit that should be at the tens place (it must appear before the unit digit).
  3. Calculate deletions needed:
    • The number of digits after the chosen unit digit.
    • The number of digits between the chosen tens and unit digits that are not part of the final special number.
  4. The answer is the minimum deletion count over all candidates. If a candidate ending cannot be formed, it is skipped.

Code Solutions

# Python solution for Minimum Operations to Make a Special Number

def minimumOperations(num: str) -> int:
    # Candidate endings that represent special numbers divisible by 25.
    candidates = ["00", "25", "50", "75"]
    n = len(num)
    min_ops = float("inf")

    # Iterate over all candidate endings
    for pattern in candidates:
        pos2 = -1  # Position for the last digit required (units place)
        pos1 = -1  # Position for the tens digit required
        
        # Search for the last digit (pattern[1]) from the end
        for i in range(n - 1, -1, -1):
            if num[i] == pattern[1]:
                pos2 = i
                break
        # If not found, this candidate can't be formed
        if pos2 == -1:
            continue
        
        # Search for the tens digit (pattern[0]) in the digits before pos2
        for j in range(pos2 - 1, -1, -1):
            if num[j] == pattern[0]:
                pos1 = j
                break
        # If tens digit is not found, move to next candidate
        if pos1 == -1:
            continue
        
        # Count deletions:
        # (n - pos2 - 1) deletions after the unit digit,
        # (pos2 - pos1 - 1) deletions between tens and unit digits.
        operations = (n - pos2 - 1) + (pos2 - pos1 - 1)
        min_ops = min(min_ops, operations)

    return min_ops if min_ops != float("inf") else -1

# Example usage:
print(minimumOperations("2245047"))  # Expected output: 2
print(minimumOperations("2908305"))  # Expected output: 3
print(minimumOperations("10"))       # Expected output: 1
← Back to All Questions