Skip to main content
Talentd

Minimum Operations to Make a Special Number - Solution & Explanation

MediumMathStringGreedyEnumeration22 min read
Practice this problem

Problem Statement

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.

 

Example 1:

Input: num = "2245047"
Output: 2
Explanation: 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
Explanation: 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
Explanation: 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.

Approach Overview

Problem Overview: You are given a numeric string and can delete any digits. The goal is to make the remaining number special, meaning it is divisible by 25. The task is to compute the minimum number of deletions required.

A number is divisible by 25 only if its last two digits are 00, 25, 50, or 75. That observation converts the problem into finding the cheapest way to keep a subsequence that ends with one of these four patterns.

Approach 1: Greedy Using Two-Pointer Technique (O(n) time, O(1) space)

The greedy insight is that only the final two digits determine divisibility by 25. Scan the string from right to left and try to form one of the valid endings: 00, 25, 50, or 75. Use two pointers: the first pointer searches for the last digit of the pair, and once found, the second pointer scans left to find the matching preceding digit. Every skipped character represents a deletion.

Compute the deletion cost for each of the four valid endings and keep the minimum. This works because keeping the rightmost valid pair always minimizes deletions to the right side of the string. The algorithm performs only linear scans over the string and uses constant extra memory. Concepts used here commonly appear in greedy and string problems.

Approach 2: Dynamic Programming Subsequence Search (O(n * k) time, O(k) space)

Another perspective treats the task as a subsequence matching problem. The valid endings form a small set of patterns: ["00", "25", "50", "75"]. For each pattern, run a dynamic programming or subsequence scan that tracks how many characters you must delete to keep the pattern in order.

Iterate through the string and attempt to match the pattern characters sequentially. If the current digit matches the next required character in the pattern, advance the pattern index; otherwise count it as a potential deletion. After processing the string, compute the number of removals required to isolate the matched subsequence. Since each pattern length is constant (2), the runtime stays linear in practice. This framing is useful when thinking about subsequences and enumeration strategies often seen in math or pattern‑matching problems.

Recommended for interviews: The greedy two-pointer approach is the expected solution. It directly uses the divisibility rule for 25 and achieves O(n) time with O(1) space. Showing the subsequence or DP interpretation demonstrates deeper reasoning, but interviewers typically want the greedy scan because it is simpler and more efficient.

Approach 1: Approach 1: Greedy using Two-Pointer Technique

In this approach, we work backwards on the string, aiming to find a pair at the end of the number that forms 00, 25, 50, or 75. These pairs are the multiples of 25. We start from the end of the string, looking to match these pairs and counting the deletions needed to make these the last two digits.

The function traverses the number string backwards and attempts to find a pair among the options '00', '25', '50', '75' that can be formed at the end of the string. For each target pair, the algorithm counts how many deletions (steps) are required to create the pair at the end of the number. A minimal count is constantly updated to ensure optimal deletions. The final count represents the minimum number of deletions required to make the number special.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n) where n is the length of the input number string. We traverse the string a few times with a fixed amount of work for each character.
Space Complexity: O(1) as we only use a few extra variables for storage, ignoring input size.

Try this approach in the editor →

Approach 2: Approach 2: Dynamic Programming Subsequence Search

This approach uses dynamic programming to explore every possible subsequence of the number, attempting to find at least one which has last two digits forming a multiple of 25. The observation is that which digits contribute to a valid subsequence can be stored in a DP table. We make a judgment based on these stored values about the minimal construction cost to create such subsequences.

This is a hypothetical placeholder, demonstrating that we consider the entire set of subsequences dimensional in a DP matrix or concept. The establishment of such a sequence matrix allows us to execute a greedy search within constrained size/variability under problem size constraints.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Due to being representative, suggested time complexity is O(n^2) with optimizations deriving from boundary conditions tested in earlier methods.
Space remains O(n^2).

Try this approach in the editor →

Approach 3: 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 ith digit of the string num, and the current number modulo 25 is k. The answer is dfs(0, 0).

The execution logic of the function dfs(i, k) is as follows:

  • If i = n, i.e., all digits of the string num have been processed, then if k = 0, the current number can be divisible by 25, return 0, otherwise return n;
  • Otherwise, the ith digit can be deleted, in this case one digit needs to be deleted, i.e., dfs(i + 1, k) + 1; if the ith digit is not deleted, then the value of k becomes (k times 10 + num[i]) bmod 25, i.e., dfs(i + 1, (k times 10 + num[i]) bmod 25). Take the minimum of these two.

To prevent repeated calculations, we can use memoization to optimize the time complexity.

The time complexity is O(n times 25), and the space complexity is O(n times 25). Here, n is the length of the string num.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Greedy using Two-Pointer Technique

Time Complexity: O(n) where n is the length of the input number string. We traverse the string a few times with a fixed amount of work for each character.
Space Complexity: O(1) as we only use a few extra variables for storage, ignoring input size.

Approach 2: Dynamic Programming Subsequence Search

Due to being representative, suggested time complexity is O(n^2) with optimizations deriving from boundary conditions tested in earlier methods.
Space remains O(n^2).

Memoization Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Two-Pointer SearchO(n)O(1)Best general solution. Quickly finds valid endings (00, 25, 50, 75) with minimal deletions.
Dynamic Programming / Subsequence MatchingO(n * k) where k=4 patternsO(k)Useful when modeling the problem as subsequence matching or extending to more patterns.

Video Solution

Leetcode Weekly contest 361 - Medium - Minimum Operations to Make a Special Number • Prakhar Agrawal • 2,582 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Make a Special Number easy or hard?
LeetCode classifies this problem as Medium difficulty. The challenge lies in recognizing the divisibility rule for 25 and translating it into a greedy scan for specific digit pairs. Once that observation is made, the implementation becomes straightforward.
Minimum Operations to Make a Special Number Python/Java solution
The typical implementation scans the string backward and attempts to build valid endings like 25 or 50. Python and Java solutions both maintain indices for the required digits and count skipped characters. The algorithm stays O(n) and uses constant extra space.
How to solve Minimum Operations to Make a Special Number in O(n)?
Check the four valid endings for numbers divisible by 25: 00, 25, 50, and 75. For each pattern, scan from the end to find the second digit, then continue scanning left to find the first digit. Count skipped digits as deletions and track the minimum cost. This approach only requires linear scans.
What is the best approach for Minimum Operations to Make a Special Number?
The greedy two-pointer approach is the most efficient solution. Scan from the right side of the string and try to form one of the valid endings (00, 25, 50, 75). Count how many digits must be deleted to keep that pair as the final digits. This runs in O(n) time with O(1) space.
Is Minimum Operations to Make a Special Number asked at Google/Amazon/Meta?
Problems involving greedy string manipulation and divisibility patterns frequently appear in interviews at companies like Amazon, Google, and Meta. This specific question tests pattern observation, string scanning, and greedy decision making, which are common interview themes.
What data structure is used in Minimum Operations to Make a Special Number?
The problem primarily uses string traversal and pointer manipulation. The greedy solution relies on two pointers scanning the string from right to left, while the alternative approach treats the target endings as subsequence patterns.
What is the time complexity of Minimum Operations to Make a Special Number?
The optimal greedy solution runs in O(n) time where n is the length of the string. You scan the string from right to left a few times to locate valid digit pairs. Space complexity remains O(1) since only a few counters and pointers are used.

Ready to solve this problem?

Practice Minimum Operations to Make a Special Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove Digit From Number to Maximize Result

Next

Remove K Digits