# Minimum Operations to Make a Special Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-operations-to-make-a-special-number)
Canonical: https://scaleengineer.com/dsa/problems/minimum-operations-to-make-a-special-number
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** String
---
## Problem
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
## Brute Force with Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    public int minimumOperations(String num) {
        int n = num.length();
        int minOps = n; // Case: delete all digits to get 0
        boolean hasZero = false;
        for (int i = 0; i < n; i++) {
            if (num.charAt(i) == '0') {
                hasZero = true;
                break;
            }
        }
        if (hasZero) {
            minOps = n - 1; // Case: keep one '0'
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int firstDigit = num.charAt(i) - '0';
                int secondDigit = num.charAt(j) - '0';
                int lastTwoDigits = firstDigit * 10 + secondDigit;

                if (lastTwoDigits % 25 == 0) {
                    // Deletions: characters between i and j, and after j
                    int deletions = (j - i - 1) + (n - 1 - j);
                    minOps = Math.min(minOps, deletions);
                }
            }
        }
        return minOps;
    }
}
```
### Algorithm
- 1. Get the length `n` of the string `num`.
- 2. 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.
- 3. Use a nested loop. The outer loop iterates with index `i` from `0` to `n-1`.
- 4. The inner loop iterates with index `j` from `i+1` to `n-1`.
- 5. Inside the inner loop, form a two-digit number using the characters `num.charAt(i)` and `num.charAt(j)`.
- 6. Check if this two-digit number is divisible by 25 (i.e., it's 0, 25, 50, or 75).
- 7. 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)`.
- 8. Update `minOps` with the minimum value found so far.
- 9. After the loops complete, return `minOps`.

## Optimized Search from Right
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.
**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.
**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.
### Explanation
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.

```java
class Solution {
    // Helper to find minimum operations for a given suffix
    private int findDeletionsForSuffix(String num, String suffix) {
        int n = num.length();
        // Find the rightmost occurrence of the second digit of the suffix
        int j = num.lastIndexOf(suffix.charAt(1));
        if (j == -1) {
            return n; // Suffix not possible
        }
        // Find the rightmost occurrence of the first digit before index j
        int i = -1;
        for (int k = j - 1; k >= 0; k--) {
            if (num.charAt(k) == suffix.charAt(0)) {
                i = k;
                break;
            }
        }
        if (i == -1) {
            return n; // Suffix not possible
        }
        // Deletions = (chars after j) + (chars between i and j)
        return (n - 1 - j) + (j - 1 - i);
    }

    public int minimumOperations(String num) {
        int n = num.length();
        int minOps = n; // Default: delete all digits

        // Case 1: Make the number 0
        if (num.contains("0")) {
            minOps = n - 1;
        }

        // Case 2: Find endings "00", "25", "50", "75"
        minOps = Math.min(minOps, findDeletionsForSuffix(num, "00"));
        minOps = Math.min(minOps, findDeletionsForSuffix(num, "25"));
        minOps = Math.min(minOps, findDeletionsForSuffix(num, "50"));
        minOps = Math.min(minOps, findDeletionsForSuffix(num, "75"));

        return minOps;
    }
}
```
### Algorithm
- 1. A number is special if it's divisible by 25, meaning it ends in "00", "25", "50", "75", or is "0".
- 2. 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').
- 3. 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)`.
- 4. Return `minOps`.

# Solutions
### Java

```java
class Solution {
private
  Integer[][] f;
private
  String num;
private
  int n;
public
  int minimumOperations(String num) {
    n = num.length();
    this.num = num;
    f = new Integer[n][25];
    return dfs(0, 0);
  }
private
  int dfs(int i, int k) {
    if (i == n) {
      return k == 0 ? 0 : n;
    }
    if (f[i][k] != null) {
      return f[i][k];
    }
    f[i][k] = dfs(i + 1, k) + 1;
    f[i][k] =
        Math.min(f[i][k], dfs(i + 1, (k * 10 + num.charAt(i) - '0') % 25));
    return f[i][k];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumOperations(string num) {
    int n = num.size();
    int f[n][25];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int k) -> int {
      if (i == n) {
        return k == 0 ? 0 : n;
      }
      if (f[i][k] != -1) {
        return f[i][k];
      }
      f[i][k] = dfs(i + 1, k) + 1;
      f[i][k] = min(f[i][k], dfs(i + 1, (k * 10 + num[i] - '0') % 25));
      return f[i][k];
    };
    return dfs(0, 0);
  }
};

```

### Python

```python
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)

```