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 theminimum number of operations required to make num special.

An integer x is considered special if it is divisible by 25.

Examples

Example 1

1
2
3
4

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

1
2
3
4

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

1
2
3
4

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.

Solution

Method 1 – Greedy & Enumeration

Intuition

To make the number divisible by 25, its last two digits must be 00, 25, 50, or 75. We try to find the minimum number of deletions needed to make the string end with any of these pairs.

Approach

  1. For each possible ending (“00”, “25”, “50”, “75”), search from the end of num for the second digit, then for the first digit before it.
  2. If both are found, count the number of digits to delete to bring them to the end.
  3. Track the minimum deletions among all endings.
  4. If not possible, answer is length of num (delete all digits to get “0”).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minimumOperations(string num) {
        vector<string> ends = {"00", "25", "50", "75"};
        int n = num.size(), ans = n;
        for (auto& e : ends) {
            int j = n - 1;
            while (j >= 0 && num[j] != e[1]) --j;
            if (j < 0) continue;
            int i = j - 1;
            while (i >= 0 && num[i] != e[0]) --i;
            if (i < 0) continue;
            ans = min(ans, n - i - 2);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func minimumOperations(num string) int {
    ends := []string{"00", "25", "50", "75"}
    n := len(num)
    ans := n
    for _, e := range ends {
        j := n - 1
        for j >= 0 && num[j] != e[1] {
            j--
        }
        if j < 0 {
            continue
        }
        i := j - 1
        for i >= 0 && num[i] != e[0] {
            i--
        }
        if i < 0 {
            continue
        }
        if n-i-2 < ans {
            ans = n - i - 2
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int minimumOperations(String num) {
        String[] ends = {"00", "25", "50", "75"};
        int n = num.length(), ans = n;
        for (String e : ends) {
            int j = n - 1;
            while (j >= 0 && num.charAt(j) != e.charAt(1)) --j;
            if (j < 0) continue;
            int i = j - 1;
            while (i >= 0 && num.charAt(i) != e.charAt(0)) --i;
            if (i < 0) continue;
            ans = Math.min(ans, n - i - 2);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minimumOperations(num: String): Int {
        val ends = listOf("00", "25", "50", "75")
        val n = num.length
        var ans = n
        for (e in ends) {
            var j = n - 1
            while (j >= 0 && num[j] != e[1]) j--
            if (j < 0) continue
            var i = j - 1
            while (i >= 0 && num[i] != e[0]) i--
            if (i < 0) continue
            ans = minOf(ans, n - i - 2)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def minimumOperations(self, num: str) -> int:
        ends = ["00", "25", "50", "75"]
        n = len(num)
        ans = n
        for e in ends:
            j = n - 1
            while j >= 0 and num[j] != e[1]:
                j -= 1
            if j < 0:
                continue
            i = j - 1
            while i >= 0 and num[i] != e[0]:
                i -= 1
            if i < 0:
                continue
            ans = min(ans, n - i - 2)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
    pub fn minimum_operations(num: String) -> i32 {
        let ends = ["00", "25", "50", "75"];
        let n = num.len();
        let num = num.as_bytes();
        let mut ans = n as i32;
        for e in ends.iter() {
            let mut j = n as i32 - 1;
            while j >= 0 && num[j as usize] != e.as_bytes()[1] {
                j -= 1;
            }
            if j < 0 { continue; }
            let mut i = j - 1;
            while i >= 0 && num[i as usize] != e.as_bytes()[0] {
                i -= 1;
            }
            if i < 0 { continue; }
            ans = ans.min(n as i32 - i - 2);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    minimumOperations(num: string): number {
        const ends = ["00", "25", "50", "75"];
        const n = num.length;
        let ans = n;
        for (const e of ends) {
            let j = n - 1;
            while (j >= 0 && num[j] !== e[1]) --j;
            if (j < 0) continue;
            let i = j - 1;
            while (i >= 0 && num[i] !== e[0]) --i;
            if (i < 0) continue;
            ans = Math.min(ans, n - i - 2);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n) — For each ending, we scan the string twice.
  • 🧺 Space complexity: O(1) — Only a few variables are used, no extra space proportional to input size.