2844. Minimum Operations to Make a Special Number

MediumGreedyMathStringEnumeration

Problem Description

You are given a string num that represents a non-negative integer, where the string is 0-indexed (meaning the first character is at position 0).

You can perform operations on this string where each operation consists of picking any single digit from num and deleting it. If you delete all digits from num, the resulting number becomes 0.

Your goal is to find the minimum number of operations (deletions) needed to make num become a "special" number.

A number is considered special if it is divisible by 25.

For example:

If num = "2908305", you might delete certain digits to get "2900" which is divisible by 25
If num = "10", you could delete the 1 to get "0" which is divisible by 25 (since 0 ÷ 25 = 0)

The problem asks you to determine the minimum number of digit deletions required to transform the given number into one that is divisible by 25.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is that we need to make the number divisible by 25. Instead of thinking about which digits to delete, we can think about which digits to keep to form a number divisible by 25.

When checking divisibility by 25, we only care about the remainder when dividing by 25. This is because a number is divisible by 25 if and only if number % 25 == 0.

As we scan through the string from left to right, we have two choices at each position:

Delete the current digit (costs us one operation)
Keep the current digit and include it in our number

When we keep a digit, it affects the remainder of our number modulo 25. If we have a current remainder k and we append a digit d, the new remainder becomes (k * 10 + d) % 25. This is because appending a digit to a number is equivalent to multiplying the number by 10 and adding the new digit.

For example, if we have the number 12 (remainder 12 when divided by 25) and we append 5, we get 125 which has remainder (12 * 10 + 5) % 25 = 125 % 25 = 0.

This naturally leads to a recursive approach where we track:

Our current position i in the string
The current remainder k when our formed number is divided by 25

At each step, we try both options (delete or keep) and take the minimum operations needed. When we reach the end of the string, if our remainder is 0, we've successfully formed a number divisible by 25. If not, we return a large value (like n, the length of the string) to indicate this path is invalid.

The memoization helps us avoid recalculating the same state (i, k) multiple times, significantly improving efficiency.

Learn more about Greedy and Math patterns.

Solution Approach

The solution uses memoization search (dynamic programming with recursion) to find the minimum number of deletions needed.

We implement a recursive function dfs(i, k) where:

i represents the current position in the string num we're processing
k represents the current remainder when our formed number is divided by 25

Implementation Details:

Base Case: When i == n (we've processed all digits):
- If k == 0, the number is divisible by 25, so return 0 (no more deletions needed)
- Otherwise, return n (indicating this path is invalid - we'd need to delete all digits)
Recursive Case: For each position i, we have two choices:
- Delete the digit: Call dfs(i + 1, k) + 1
  - We move to the next position without changing the remainder k
  - Add 1 to count this deletion operation
- Keep the digit: Call dfs(i + 1, (k * 10 + int(num[i])) % 25)
  - We include this digit in our number
  - Update the remainder using the formula: (k * 10 + digit) % 25
  - No deletion cost is added
Take the minimum of both choices: min(delete_option, keep_option)
Memoization: The @cache decorator stores results for each unique (i, k) pair to avoid redundant calculations. Since k can only be in range [0, 24] (remainder when dividing by 25), and i can be in range [0, n-1], we have at most n * 25 unique states.

Starting Point: We call dfs(0, 0) to start from the first digit with an initial remainder of 0.

Time Complexity: O(25 * n) = O(n) where n is the length of the string, since we have at most 25n states and each state is computed once.

Space Complexity: O(25 * n) = O(n) for the memoization cache.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's trace through the solution with num = "1234".

We want to find the minimum deletions to make this number divisible by 25.

Starting with dfs(0, 0) - we're at position 0 with remainder 0.

Position 0 (digit '1'):

Option 1: Delete '1' → dfs(1, 0) + 1
Option 2: Keep '1' → dfs(1, 1) (since (0 * 10 + 1) % 25 = 1)

Let's explore Option 2 first: dfs(1, 1)

Position 1 (digit '2'), remainder = 1:

Option 1: Delete '2' → dfs(2, 1) + 1
Option 2: Keep '2' → dfs(2, 12) (since (1 * 10 + 2) % 25 = 12)

Following Option 2: dfs(2, 12)

Position 2 (digit '3'), remainder = 12:

Option 1: Delete '3' → dfs(3, 12) + 1
Option 2: Keep '3' → dfs(3, 23) (since (12 * 10 + 3) % 25 = 123 % 25 = 23)

Following Option 2: dfs(3, 23)

Position 3 (digit '4'), remainder = 23:

Option 1: Delete '4' → dfs(4, 23) + 1
Option 2: Keep '4' → dfs(4, 9) (since (23 * 10 + 4) % 25 = 234 % 25 = 9)

Following Option 2: dfs(4, 9)

Base case: We've reached the end with remainder 9 ≠ 0, so return 4 (invalid path).

Now let's backtrack and explore a different path. If we keep '1' and '2' to get "12", then delete '3' and '4':

Keep '1': remainder becomes 1
Keep '2': remainder becomes 12
Delete '3': remainder stays 12, cost +1
Delete '4': remainder stays 12, cost +1
End with remainder 12 ≠ 0, total cost = 2 + large value (invalid)

Let's try keeping only '2' and '5' if we modify our example to num = "1250":

Delete '1': remainder stays 0, cost +1
Keep '2': remainder becomes 2
Keep '5': remainder becomes (2 * 10 + 5) % 25 = 25 % 25 = 0
Keep '0': remainder becomes (0 * 10 + 0) % 25 = 0
End with remainder 0, total cost = 1

The answer would be 1 deletion (removing the '1' to get "250" which is divisible by 25).

Solution Implementation

1from functools import cache
2from typing import Optional
3
4
5class Solution:
6    def minimumOperations(self, num: str) -> int:
7        """
8        Find minimum number of digit deletions to make the number divisible by 25.
9      
10        Args:
11            num: String representation of the number
12          
13        Returns:
14            Minimum number of operations (deletions) needed
15        """
16      
17        @cache
18        def find_min_deletions(index: int, remainder: int) -> int:
19            """
20            Recursively find minimum deletions needed from current position.
21          
22            Args:
23                index: Current position in the string
24                remainder: Current remainder when divided by 25
25              
26            Returns:
27                Minimum number of deletions needed from this state
28            """
29            # Base case: reached end of string
30            if index == string_length:
31                # If remainder is 0, number is divisible by 25, no more deletions needed
32                # Otherwise, we need to delete all digits (return string_length)
33                return 0 if remainder == 0 else string_length
34          
35            # Option 1: Delete current digit (add 1 to deletion count)
36            deletions_if_skip = find_min_deletions(index + 1, remainder) + 1
37          
38            # Option 2: Keep current digit and update remainder
39            current_digit = int(num[index])
40            new_remainder = (remainder * 10 + current_digit) % 25
41            deletions_if_keep = find_min_deletions(index + 1, new_remainder)
42          
43            # Return minimum of both options
44            return min(deletions_if_skip, deletions_if_keep)
45      
46        # Store string length for efficiency
47        string_length = len(num)
48      
49        # Start recursion from index 0 with remainder 0
50        return find_min_deletions(0, 0)
51

1class Solution {
2    // Memoization table: dp[index][remainder] stores minimum operations
3    // when at index 'index' with current number having remainder 'remainder' when divided by 25
4    private Integer[][] dp;
5    private String num;
6    private int length;
7
8    /**
9     * Finds the minimum number of operations (deletions) needed to make the number divisible by 25.
10     * A number is divisible by 25 if it ends with 00, 25, 50, or 75.
11     * 
12     * @param num The input number as a string
13     * @return The minimum number of deletions required
14     */
15    public int minimumOperations(String num) {
16        length = num.length();
17        this.num = num;
18        dp = new Integer[length][25];
19        return dfs(0, 0);
20    }
21
22    /**
23     * Recursive function with memoization to find minimum operations.
24     * 
25     * @param index Current position in the string
26     * @param remainder Current remainder when the formed number is divided by 25
27     * @return Minimum number of deletions needed from this state
28     */
29    private int dfs(int index, int remainder) {
30        // Base case: reached end of string
31        if (index == length) {
32            // If remainder is 0, number is divisible by 25, no deletions needed
33            // Otherwise, we need to delete all digits (return length)
34            return remainder == 0 ? 0 : length;
35        }
36      
37        // Check if already computed
38        if (dp[index][remainder] != null) {
39            return dp[index][remainder];
40        }
41      
42        // Option 1: Delete current digit (add 1 to deletion count)
43        dp[index][remainder] = dfs(index + 1, remainder) + 1;
44      
45        // Option 2: Keep current digit and update remainder
46        int currentDigit = num.charAt(index) - '0';
47        int newRemainder = (remainder * 10 + currentDigit) % 25;
48        dp[index][remainder] = Math.min(dp[index][remainder], dfs(index + 1, newRemainder));
49      
50        return dp[index][remainder];
51    }
52}
53

1class Solution {
2public:
3    int minimumOperations(string num) {
4        int n = num.size();
5      
6        // dp[i][remainder] = minimum operations to make substring from index i to end
7        // have a remainder of 'remainder' when divided by 25
8        int dp[n][25];
9        memset(dp, -1, sizeof(dp));
10      
11        // Recursive function with memoization
12        // i: current index in the string
13        // remainder: current remainder when divided by 25
14        auto dfs = [&](this auto&& dfs, int i, int remainder) -> int {
15            // Base case: reached end of string
16            if (i == n) {
17                // If remainder is 0, number is divisible by 25, no operations needed
18                // Otherwise, need to delete all digits
19                return remainder == 0 ? 0 : n;
20            }
21          
22            // Return memoized result if already computed
23            if (dp[i][remainder] != -1) {
24                return dp[i][remainder];
25            }
26          
27            // Option 1: Delete current digit (cost = 1)
28            dp[i][remainder] = dfs(i + 1, remainder) + 1;
29          
30            // Option 2: Keep current digit and update remainder
31            int currentDigit = num[i] - '0';
32            int newRemainder = (remainder * 10 + currentDigit) % 25;
33            dp[i][remainder] = min(dp[i][remainder], dfs(i + 1, newRemainder));
34          
35            return dp[i][remainder];
36        };
37      
38        // Start from index 0 with initial remainder 0
39        return dfs(0, 0);
40    }
41};
42

1/**
2 * Finds the minimum number of operations to make a number divisible by 25
3 * @param num - The input number as a string
4 * @returns The minimum number of digit deletions needed
5 */
6function minimumOperations(num: string): number {
7    const numLength: number = num.length;
8  
9    // Memoization table: memo[position][remainder]
10    // Stores the minimum operations needed from position i with current remainder k
11    const memo: number[][] = Array.from(
12        { length: numLength }, 
13        () => Array.from({ length: 25 }, () => -1)
14    );
15  
16    /**
17     * Dynamic programming function to find minimum deletions
18     * @param position - Current position in the string
19     * @param remainder - Current remainder when divided by 25
20     * @returns Minimum number of deletions needed from this state
21     */
22    const findMinDeletions = (position: number, remainder: number): number => {
23        // Base case: reached end of string
24        if (position === numLength) {
25            // If remainder is 0, the number is divisible by 25
26            return remainder === 0 ? 0 : numLength;
27        }
28      
29        // Return memoized result if already computed
30        if (memo[position][remainder] !== -1) {
31            return memo[position][remainder];
32        }
33      
34        // Option 1: Delete current digit (add 1 to operation count)
35        let deleteCurrentDigit: number = findMinDeletions(position + 1, remainder) + 1;
36      
37        // Option 2: Keep current digit and update remainder
38        const currentDigit: number = Number(num[position]);
39        const newRemainder: number = (remainder * 10 + currentDigit) % 25;
40        let keepCurrentDigit: number = findMinDeletions(position + 1, newRemainder);
41      
42        // Store and return the minimum of both options
43        memo[position][remainder] = Math.min(deleteCurrentDigit, keepCurrentDigit);
44        return memo[position][remainder];
45    };
46  
47    // Start the recursive search from position 0 with remainder 0
48    return findMinDeletions(0, 0);
49}
50

Time and Space Complexity

The time complexity is O(n × 25), where n is the length of the string num. This is because the recursive function dfs(i, k) has two parameters: i ranges from 0 to n, and k represents the remainder when divided by 25, which can have at most 25 different values (0 through 24). Due to the @cache decorator, each unique combination of (i, k) is computed only once, resulting in at most n × 25 different states.

The space complexity is O(n × 25). This consists of two components: the memoization cache stores up to n × 25 entries (one for each possible state), and the recursion depth can go up to n levels deep, contributing O(n) to the call stack. Since O(n × 25) + O(n) = O(n × 25), the overall space complexity is O(n × 25).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Leading Zeros

The Pitfall: When we delete digits and keep others, we might create numbers with leading zeros. For example, if num = "2050" and we delete the first two digits to get "50", this is valid. However, if we delete the 2 and 5 to get "00", this represents the number 0, not 00. The current solution doesn't explicitly handle this distinction, but it works correctly because:

The remainder calculation (remainder * 10 + current_digit) % 25 naturally handles leading zeros
"00", "000", etc. all evaluate to 0, which is divisible by 25

Why it's not actually a problem here: The modulo arithmetic handles this implicitly, but developers might overthink this case.

2. Misunderstanding the Invalid Path Return Value

The Pitfall: In the base case, when remainder != 0, the function returns string_length (not infinity). This might seem counterintuitive - why return the total length instead of a large number like float('inf')?

The Issue: If someone changes this to return float('inf'), the code breaks because:

# This would cause issues:
deletions_if_skip = find_min_deletions(index + 1, remainder) + 1
# If find_min_deletions returns inf, then inf + 1 is still inf (correct)
# BUT when comparing with valid paths, we lose precision about actual deletion counts

The Solution: The return value of string_length is clever because:

It represents deleting ALL digits (making the number 0)
Since 0 is divisible by 25, this is always a valid fallback
It ensures we always have a valid answer, even if no other combination works

3. Not Considering the Empty String/Zero Case

The Pitfall: What happens if we delete all digits? The problem states this results in 0, which IS divisible by 25.

Potential Bug Pattern:

# WRONG: Someone might think empty string is invalid
if index == string_length:
    return 0 if remainder == 0 else float('inf')  # This would be wrong!

The Correct Understanding: The current solution handles this correctly by returning string_length when no valid number can be formed, which represents deleting everything to get 0.

4. Cache Key Collision Concerns

The Pitfall: Developers might worry that using just (index, remainder) as cache key isn't sufficient - what if we form the same remainder at the same position through different paths?

Why it's not a problem: The beauty of this DP approach is that it doesn't matter HOW we got to a particular (index, remainder) state. The minimum deletions needed from that point forward only depends on:

Where we are in the string (index)
What our current remainder is (remainder)

The history of how we achieved this remainder is irrelevant for future decisions.

5. Integer Overflow Concerns (Language-Specific)

The Pitfall: In languages with fixed integer sizes, continuously computing remainder * 10 + digit might seem like it could overflow.

Why it's safe: Since we take modulo 25 at each step: (remainder * 10 + current_digit) % 25, the remainder is always bounded between 0 and 24. The maximum value before taking modulo would be 24 * 10 + 9 = 249, which fits in any standard integer type.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan: