Scale Engineer

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

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

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.

Solutions

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

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 →

Next problem