2844. Minimum Operations to Make a Special Number

Description

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.

Solutions

Solution 1: 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 \(i\)th 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 \(i\)th digit can be deleted, in this case one digit needs to be deleted, i.e., \(dfs(i + 1, k) + 1\); if the \(i\)th digit is not deleted, then the value of \(k\) becomes \((k \times 10 + \textit{num}[i]) \bmod 25\), i.e., \(dfs(i + 1, (k \times 10 + \textit{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\).

Python3JavaC++GoTypeScript

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)

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];
    }
}

class Solution {
public:
    int minimumOperations(string num) {
        int n = num.size();
        int f[n][25];
        memset(f, -1, sizeof(f));
        auto dfs = [&](this auto&& 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);
    }
};

func minimumOperations(num string) int {
    n := len(num)
    f := make([][25]int, n)
    for i := range f {
        for j := range f[i] {
            f[i][j] = -1
        }
    }
    var dfs func(i, k int) int
    dfs = func(i, k int) int {
        if i == n {
            if k == 0 {
                return 0
            }
            return 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+int(num[i]-'0'))%25))
        return f[i][k]
    }
    return dfs(0, 0)
}

function minimumOperations(num: string): number {
    const n = num.length;
    const f: number[][] = Array.from({ length: n }, () => Array.from({ length: 25 }, () => -1));
    const dfs = (i: number, k: number): number => {
        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] = Math.min(f[i][k], dfs(i + 1, (k * 10 + Number(num[i])) % 25));
        return f[i][k];
    };
    return dfs(0, 0);
}

2844. Minimum Operations to Make a Special Number

Description

Solutions

Solution 1: Memoization Search

Comments