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 <= 100num only consists of digits '0' through '9'.num does not contain any leading zeros.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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).
| Approach | Complexity |
|---|---|
| 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. |
| 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. |
Minimum Operations to Make Array Equal | Leetcode - 1551 • Algorithms Made Easy • 24,165 views views
Watch 9 more video solutions →Practice Minimum Operations to Make a Special Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor