Question

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$.

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

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