Minimum Operations to Make a Special Number

Med

#2543Time: O(n^2), where n is the length of the input string `num`. The nested loops iterate through all possible pairs of indices, which is the dominant factor in the runtime.Space: O(1), as we only use a few variables to store state, regardless of the input size.

Patterns

Math Greedy Enumeration

Data structures

String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach iterates through all possible pairs of indices (i, j) with i < j in the input string num. For each pair, it checks if the two digits num[i] and num[j] can form the last two digits of a special number (i.e., a number divisible by 25). If they can, it calculates the number of deletions required and updates the minimum found so far. The special case of forming the number '0' is also handled as a baseline.

Algorithm

1. Get the length n of the string num.
1. Initialize a variable minOps to n. If num contains '0', update minOps to n-1. This handles the base case of forming the number 0.
1. Use a nested loop. The outer loop iterates with index i from 0 to n-1.
1. The inner loop iterates with index j from i+1 to n-1.
1. Inside the inner loop, form a two-digit number using the characters num.charAt(i) and num.charAt(j).
1. Check if this two-digit number is divisible by 25 (i.e., it's 0, 25, 50, or 75).
1. If it is, a valid subsequence ending is found. The number of deletions required is the count of characters between indices i and j, plus the count of characters after index j. This is calculated as (j - i - 1) + (n - 1 - j).
1. Update minOps with the minimum value found so far.
1. After the loops complete, return minOps.

Walkthrough

A number is considered special if it's divisible by 25. This implies that the number must end in "00", "25", "50", "75", or it could be the number "0" itself.

This brute-force method systematically explores all possibilities for the last two digits. We initialize the minimum operations minOps by considering the simplest special number, "0". If the input string num contains a '0', we can achieve this by deleting all other n-1 characters. If not, we'd have to delete all n characters.

Next, we use nested loops to examine every pair of characters (num[i], num[j]) where i < j. This pair represents a potential two-digit ending for our special number. For each pair, we form the two-digit number and check if it's one of 0, 25, 50, or 75. If it is, we've found a valid subsequence. The number of characters to delete are those between index i and j, and all characters after index j. The count of characters to delete is (j - i - 1) (between i and j) plus (n - 1 - j) (after j). We keep track of the minimum deletions found across all valid pairs and return this minimum value.

1class Solution {2    public int minimumOperations(String num) {3        int n = num.length();4        int minOps = n; // Case: delete all digits to get 05        boolean hasZero = false;6        for (int i = 0; i < n; i++) {7            if (num.charAt(i) == '0') {8                hasZero = true;9                break;10            }11        }12        if (hasZero) {13            minOps = n - 1; // Case: keep one '0'14        }15 16        for (int i = 0; i < n; i++) {17            for (int j = i + 1; j < n; j++) {18                int firstDigit = num.charAt(i) - '0';19                int secondDigit = num.charAt(j) - '0';20                int lastTwoDigits = firstDigit * 10 + secondDigit;21 22                if (lastTwoDigits % 25 == 0) {23                    // Deletions: characters between i and j, and after j24                    int deletions = (j - i - 1) + (n - 1 - j);25                    minOps = Math.min(minOps, deletions);26                }27            }28        }29        return minOps;30    }31}

Complexity

Time

O(n^2), where n is the length of the input string `num`. The nested loops iterate through all possible pairs of indices, which is the dominant factor in the runtime.

Space

O(1), as we only use a few variables to store state, regardless of the input size.

Trade-offs

Pros

Simple to understand and implement.
Correctly solves the problem by exhaustively checking all valid two-digit endings.

Cons

Inefficient for large strings due to its quadratic time complexity, which might be too slow if the constraints were larger.

This approach improves upon the brute-force method by observing that to minimize deletions, we should try to keep digits that are as far to the right as possible. Instead of checking all pairs, we specifically search for the four special endings ("00", "25", "50", "75") by scanning the string from right to left. This allows us to find the optimal placement for the last two digits in linear time.

Algorithm

1. A number is special if it's divisible by 25, meaning it ends in "00", "25", "50", "75", or is "0".
1. Initialize a variable minOps to n (representing deleting all digits). If the string contains a '0', update minOps to n-1 (representing keeping one '0').
1. For each target suffix s in {"00", "25", "50", "75"}:
- a. Find the index of the rightmost occurrence of the last character of the suffix, s[1]. Let this be j.
- b. If s[1] is not found, this suffix cannot be formed. Continue to the next suffix.
- c. Find the index of the rightmost occurrence of the first character of the suffix, s[0], in the substring of num before index j. Let this be i.
- d. If s[0] is not found, this suffix cannot be formed. Continue.
- e. If both are found, calculate the number of deletions: (n - 1 - j) (deletions after j) + (j - 1 - i) (deletions between i and j).
- f. Update minOps = min(minOps, calculated_deletions).
1. Return minOps.

Walkthrough

The core idea is that a number divisible by 25 must end in "00", "25", "50", or "75". To minimize deletions, we need to find a subsequence of num that ends in one of these, using the rightmost possible digits.

For any target ending XY, we should find the rightmost Y in the string, and then the rightmost X that appears before it. This maximizes the indices of the chosen digits, which in turn minimizes the number of characters that need to be deleted.

We can implement this by creating a helper function that takes a target suffix (e.g., "50") and calculates the minimum deletions to form it. This function would first find the last occurrence of '0' (at index j), then find the last occurrence of '5' before index j (at index i). The deletions would be the sum of characters to the right of j and characters between i and j.

We do this for all four suffixes ("00", "25", "50", "75") and take the minimum result. We also compare this with the operations needed to form "0" (which is n-1 if a '0' exists). The overall minimum is the answer.

1class Solution {2    // Helper to find minimum operations for a given suffix3    private int findDeletionsForSuffix(String num, String suffix) {4        int n = num.length();5        // Find the rightmost occurrence of the second digit of the suffix6        int j = num.lastIndexOf(suffix.charAt(1));7        if (j == -1) {8            return n; // Suffix not possible9        }10        // Find the rightmost occurrence of the first digit before index j11        int i = -1;12        for (int k = j - 1; k >= 0; k--) {13            if (num.charAt(k) == suffix.charAt(0)) {14                i = k;15                break;16            }17        }18        if (i == -1) {19            return n; // Suffix not possible20        }21        // Deletions = (chars after j) + (chars between i and j)22        return (n - 1 - j) + (j - 1 - i);23    }24 25    public int minimumOperations(String num) {26        int n = num.length();27        int minOps = n; // Default: delete all digits28 29        // Case 1: Make the number 030        if (num.contains("0")) {31            minOps = n - 1;32        }33 34        // Case 2: Find endings "00", "25", "50", "75"35        minOps = Math.min(minOps, findDeletionsForSuffix(num, "00"));36        minOps = Math.min(minOps, findDeletionsForSuffix(num, "25"));37        minOps = Math.min(minOps, findDeletionsForSuffix(num, "50"));38        minOps = Math.min(minOps, findDeletionsForSuffix(num, "75"));39 40        return minOps;41    }42}

Complexity

Time

O(n), where n is the length of the input string `num`. For each of the 4 constant suffixes, we perform searches (like `lastIndexOf` or a manual scan) which take O(n) time. Since the number of suffixes is constant, the total time complexity is linear.

Space

O(1). The algorithm uses a constant amount of extra space for variables. The helper function operates in-place on the input string without significant auxiliary storage.

Trade-offs

Pros

Highly efficient with a linear time complexity, making it suitable for larger inputs.
The logic is direct and based on the mathematical properties of numbers divisible by 25.

Cons

The implementation requires careful handling of string searches and indices to ensure correctness.

Solutions

Solution

1class Solution {2private3  Integer[][] f;4private5  String num;6private7  int n;8public9  int minimumOperations(String num) {10    n = num.length();11    this.num = num;12    f = new Integer[n][25];13    return dfs(0, 0);14  }15private16  int dfs(int i, int k) {17    if (i == n) {18      return k == 0 ? 0 : n;19    }20    if (f[i][k] != null) {21      return f[i][k];22    }23    f[i][k] = dfs(i + 1, k) + 1;24    f[i][k] =25        Math.min(f[i][k], dfs(i + 1, (k * 10 + num.charAt(i) - '0') % 25));26    return f[i][k];27  }28}

1class Solution {2public:3  int minimumOperations(string num) {4    int n = num.size();5    int f[n][25];6    memset(f, -1, sizeof(f));7    function<int(int, int)> dfs = [&](int i, int k) -> int {8      if (i == n) {9        return k == 0 ? 0 : n;10      }11      if (f[i][k] != -1) {12        return f[i][k];13      }14      f[i][k] = dfs(i + 1, k) + 1;15      f[i][k] = min(f[i][k], dfs(i + 1, (k * 10 + num[i] - '0') % 25));16      return f[i][k];17    };18    return dfs(0, 0);19  }20};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem