LeetCode 2844 - Minimum Operations to Make a Special Number

The problem asks us to transform a string num representing a non-negative integer into a special number by deleting as few digits as possible. A special number is defined as an integer divisible by 25.

leetcodemediummathstringgreedyenumeration

LeetCode Problem 2844

Difficulty: 🟡 Medium
Topics: Math, String, Greedy, Enumeration

Solution

Problem Understanding

The problem asks us to transform a string num representing a non-negative integer into a special number by deleting as few digits as possible. A special number is defined as an integer divisible by 25. In decimal notation, a number is divisible by 25 if its last two digits are one of 00, 25, 50, or 75.

The input is a string num of length between 1 and 100, consisting only of digits 0-9, and it has no leading zeros. The output is the minimum number of deletions required to make num special. If we delete all digits, the number becomes 0, which is divisible by 25.

Important observations include that the problem can be reduced to positioning two digits at the end of the string that form one of the valid pairs 00, 25, 50, 75 while deleting the fewest digits possible. Edge cases include very short numbers, numbers that already end with a valid pair, and numbers containing only zeros.

Approaches

A brute-force approach would consider all possible subsequences of num of length at least 2, check whether the last two digits form a valid pair divisible by 25, and keep track of the minimum number of deletions. While correct, this approach has exponential time complexity, O(2^n), and is infeasible for n up to 100.

The optimal approach relies on the key observation that only the last two digits matter for divisibility by 25. We can iterate over num backwards, searching for a valid last digit of a pair and then a matching first digit. For each valid target pair (00, 25, 50, 75), we compute the number of digits that need to be removed to move those two digits to the end of the number while maintaining order. The minimum across all target pairs gives the answer. This method is linear in the length of the string and works efficiently for n up to 100.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Generate all subsequences and check divisibility
Optimal O(n) O(1) Iterate backwards for valid pairs, track deletions

Algorithm Walkthrough

  1. Define a list of target pairs representing valid last two digits for numbers divisible by 25: ["00", "25", "50", "75"].
  2. Initialize a variable min_ops to a very large number to track the minimum deletions needed.
  3. For each target pair (tens, ones), iterate backwards over num to find a digit equal to ones. The index of this digit will be the position of the last digit of the special number.
  4. After finding ones, continue iterating backwards to find a digit equal to tens that appears before ones.
  5. Compute the number of deletions required to move these two digits to the last two positions. This is len(num) - index_of_tens - 2.
  6. Update min_ops if the current deletions count is smaller than the previous minimum.
  7. After checking all pairs, return min_ops.

Why it works: The algorithm ensures that we only consider deletions that preserve the order of digits. By iterating backwards and stopping at the first occurrence of a valid pair for each target, we guarantee the minimal number of deletions because any other valid pair occurring earlier would require deleting more digits.

Python Solution

class Solution:
    def minimumOperations(self, num: str) -> int:
        n = len(num)
        targets = ["00", "25", "50", "75"]
        min_ops = float('inf')
        
        for t in targets:
            ones, tens = t[1], t[0]
            i = n - 1
            while i >= 0 and num[i] != ones:
                i -= 1
            if i < 0:
                continue
            j = i - 1
            while j >= 0 and num[j] != tens:
                j -= 1
            if j < 0:
                continue
            deletions = (n - 1 - i) + (i - 1 - j)
            min_ops = min(min_ops, deletions)
        
        return min_ops

Implementation Explanation: We loop over each target pair. The first while loop searches for the last digit of the pair from the end of the string. The second while loop searches for the tens digit before the ones digit. We compute deletions as the number of digits between these digits plus the digits after the last one. We maintain the minimum across all valid pairs.

Go Solution

func minimumOperations(num string) int {
    n := len(num)
    targets := []string{"00", "25", "50", "75"}
    minOps := n + 1
    
    for _, t := range targets {
        ones, tens := t[1], t[0]
        i := n - 1
        for i >= 0 && num[i] != ones {
            i--
        }
        if i < 0 {
            continue
        }
        j := i - 1
        for j >= 0 && num[j] != tens {
            j--
        }
        if j < 0 {
            continue
        }
        deletions := (n - 1 - i) + (i - 1 - j)
        if deletions < minOps {
            minOps = deletions
        }
    }
    
    return minOps
}

Go Differences: The Go implementation mirrors the Python logic closely. We use slices to represent target pairs, standard for loops to iterate backward, and simple integer variables for indices and deletions. No special handling is needed for empty slices since we skip invalid targets.

Worked Examples

Example 1: num = "2245047"

Target pairs: "00","25","50","75"

  • For "00": No zeros at the end in the right position, skipped.
  • For "25": Find '5' at index 4, find '2' before it at index 1 → deletions = (6-4) + (3-1) = 2+2 = 4. Not minimal.
  • For "50": Find '0' at index 3, find '5' before it at index 2 → deletions = (6-3) + (2-2) = 3+0 = 3. Better.
  • For "75": Not found.

Minimal deletions: 2 → resulting number "22450".

Example 2: num = "2908305"

Target pairs: "00","25","50","75"

  • "00": Not possible.
  • "25": '5' at index 6, '2' before → index 0, deletions = (6-6)+(5-0)=0+5=5
  • "50": '0' at index 4, '5' before → index 3, deletions = (6-4)+(3-3)=2+0=2
  • "75": Not found.

Minimal deletions: 3 → resulting number "2900".

Example 3: num = "10"

  • "00": Not found
  • "25": Not found
  • "50": '0' at index 1, '5' not found before → skipped
  • "75": Not found

Minimal deletions: 1 → resulting number "0"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through the string up to 4 times (once per target pair)
Space O(1) Constant extra space for indices and minimal variables

Since the string length is at most 100, this linear approach is very efficient.

Test Cases

# provided examples
assert Solution().minimumOperations("2245047") == 2  # minimal deletions to form 22450
assert Solution().minimumOperations("2908305") == 3  # minimal deletions to form 2900
assert Solution().minimumOperations("10") == 1       # minimal deletions to form 0

# boundary tests
assert Solution().minimumOperations("0") == 0        # already divisible by 25
assert Solution().minimumOperations("25") == 0       # no deletion needed
assert Solution().minimumOperations("1") == 1        # single digit non-divisible, delete to form 0
assert Solution().minimumOperations("100") == 0      # divisible by 25
assert Solution().minimumOperations("7525") == 0     # already divisible by 25
assert Solution().minimumOperations("5075") == 0     # already divisible by 25
Test Why
"2245047" Standard example with deletions required
"2908305" Requires multiple deletions for a valid ending
"10" Short string ending in zero
"0" Edge case, already divisible
"25" Minimal deletions for exactly divisible number
"1" Single-digit, non-divisible
"100" Number with trailing zeros
"7525" Already special number
"5075" Already special number