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

Minimum Operations to Make a Special Number

Difficulty: Medium

Problem Description

You are given a 0-indexed string num representing a non-negative integer. In one operation, you can pick any digit of num and delete it. Note that if you delete all the digits of num, num becomes 0. Return the minimum number of operations required to make num special. An integer x is considered special if it is divisible by 25.

Key Insights

  • A number is divisible by 25 if it ends in 00, 25, 50, or 75.
  • The goal is to find the minimum number of deletions needed to form a number that ends with one of these pairs.
  • We can iterate through the digits of the number and track the last occurrences of the required pairs.
  • The operations needed will be based on how many digits we have to skip or delete to form the special number.

Space and Time Complexity

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

Solution

To solve the problem, we can use a greedy approach:

  1. Start from the end of the string num and look for the pairs 00, 25, 50, or 75.
  2. For each pair, count how many digits we need to skip to reach the first digit of the pair and the second digit.
  3. Keep track of the minimum deletions required for each valid pair found.
  4. Return the minimum deletions needed to form a special number.

Code Solutions

def minimumOperations(num: str) -> int:
    # Possible endings to form a special number
    special_ends = ['00', '25', '50', '75']
    min_operations = float('inf')  # Initialize to a large number

    for end in special_ends:
        # Count how many deletions are needed for this special ending
        operations = 0
        j = len(num) - 1  # Pointer for the end of the string
        for digit in reversed(end):
            # Move j to find the digit that matches
            while j >= 0 and num[j] != digit:
                operations += 1  # We would delete this digit
                j -= 1
            # Move past the matched digit
            if j >= 0:
                j -= 1
            else:
                operations = float('inf')  # Not possible to form this ending
                break
        # Count remaining digits as deletions
        operations += j + 1  # All digits before the matched digits are deleted
        min_operations = min(min_operations, operations)

    return min_operations
← Back to All Questions