#2844

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Minimum Operations to Make a Special Number

Minimize operations to make a number divisible by 25 by deleting digits. Use greedy choice and invariant validation.

Problem Statement

You are given a string num representing a non-negative integer. In one operation, you can delete any single digit from num. If you delete all digits, the number becomes 0.

The goal is to return the minimum number of deletions required to make the number divisible by 25. A number is divisible by 25 if it ends with either '00', '25', '50', or '75'.

Examples

Example 1

Input: num = "2245047"

Output: 2

Delete digits num[5] and num[6]. The resulting number is "22450" which is special since it is divisible by 25. It can be shown that 2 is the minimum number of operations required to get a special number.

Example 2

Input: num = "2908305"

Output: 3

Delete digits num[3], num[4], and num[6]. The resulting number is "2900" which is special since it is divisible by 25. It can be shown that 3 is the minimum number of operations required to get a special number.

Example 3

Input: num = "10"

Output: 1

Delete digit num[0]. The resulting number is "0" which is special since it is divisible by 25. It can be shown that 1 is the minimum number of operations required to get a special number.

Constraints

1 <= num.length <= 100
num only consists of digits '0' through '9'.
num does not contain any leading zeros.

Solution Approach

Greedy Choice

To minimize deletions, check for the smallest sequence of digits that form one of the valid endings: '00', '25', '50', or '75'. Greedily remove digits that are not part of this sequence.

Invariant Validation

Maintain an invariant where at each step, the last digits of the number progressively align with one of the valid ending pairs. This ensures the minimal deletions to achieve a divisible number.

Efficient Search

Search for pairs of digits from the end of the string that form valid endings and count the deletions necessary to keep them. This can be done in O(n) time by scanning from the rightmost digit.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the approach used for searching valid digit pairs, typically O(n). Space complexity is O(1) if only a few variables are used to track positions and counts.

What Interviewers Usually Probe

Candidates who optimize the search for valid digit pairs using greedy strategies show understanding of the problem's mathematical properties.
Look for candidates to validate their greedy approach by ensuring the fewest deletions are performed.
Candidates who struggle with identifying the valid divisibility conditions may need guidance on greedy algorithms.

Common Pitfalls or Variants

Common pitfalls

Not considering the correct order of deletions can lead to extra operations. Ensure deletions are minimized by focusing on the last digits first.
Overlooking edge cases such as the presence of a single zero digit. A single zero should result in at most n - 1 deletions.
Incorrectly identifying valid divisibility endings. Ensure the number ends with '00', '25', '50', or '75' for divisibility by 25.

Follow-up variants

Consider handling numbers that already satisfy the divisibility condition to avoid unnecessary deletions.
Explore cases where the number has multiple valid digit pairs and ensure the minimal deletions are performed.
Handle large numbers efficiently, as the length of num can be up to 100 digits.

FAQ

What is the minimum number of deletions required for the problem 'Minimum Operations to Make a Special Number'?

The minimum number of deletions is determined by removing all digits that do not help form a valid divisible number, which ends in '00', '25', '50', or '75'.

How can a greedy approach help solve 'Minimum Operations to Make a Special Number'?

A greedy approach ensures you delete digits that do not form a valid ending, minimizing the number of deletions to make the number divisible by 25.

What are the valid endings for divisibility by 25?

The valid endings are '00', '25', '50', and '75'. These endings are required to make the number divisible by 25.

What if the number already ends with a valid ending in 'Minimum Operations to Make a Special Number'?

If the number already ends with a valid ending, no deletions are needed, and the answer is zero operations.

How does GhostInterview help with problems like 'Minimum Operations to Make a Special Number'?

GhostInterview provides guidance through the problem-solving process, offering hints, explanations, and real-time feedback to help you arrive at an optimal solution.

terminal

Solution

Solution 1: Memoization Search

We notice that an integer $x$ can be divisible by $25$, i.e., $x \bmod 25 = 0$. Therefore, we can design a function $dfs(i, k)$, which represents the minimum number of digits to be deleted to make the number a special number, starting from the $i$th digit of the string $num$, and the current number modulo $25$ is $k$. The answer is $dfs(0, 0)$.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def minimumOperations(self, num: str) -> int:
        @cache
        def dfs(i: int, k: int) -> int:
            if i == n:
                return 0 if k == 0 else n
            ans = dfs(i + 1, k) + 1
            ans = min(ans, dfs(i + 1, (k * 10 + int(num[i])) % 25))
            return ans

        n = len(num)
        return dfs(0, 0)

Continue Practicing

#2842 count k subsequences of a string with maximum beauty #2864 maximum odd binary number #2800 shortest string that contains three strings