Minimum Operations to Make a Special Number

Minimum Operations to Make a Special Number - 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.

Input & Output

Example 1 — Basic Pattern

$ Input: num = "2245047"

› Output: 2

💡 Note: We can form "2250" by deleting the digits '4' and '7'. Since 2250 % 25 = 0, we need 2 operations.

Example 2 — Single Zero

$ Input: num = "2908305"

› Output: 3

💡 Note: We can form "2900" by deleting '8', '3', '5'. Since 2900 % 25 = 0, we need 3 operations.

Example 3 — Already Special

$ Input: num = "10"

› Output: 1

💡 Note: 10 is not divisible by 25. We delete '1' to get '0', and 0 % 25 = 0, so we need 1 operation.

Constraints

1 ≤ num.length ≤ 10⁵
num consists of only digits
num does not contain any leading zeros

Visualization

Tap to expand

Understanding the Visualization

Input

String num representing a non-negative integer

Process

Find pattern ending (00, 25, 50, 75) with minimum deletions

Output

Minimum operations needed

Key Takeaway

🎯 Key Insight: Numbers divisible by 25 must end in 00, 25, 50, or 75 - find these patterns greedily

Asked in

G Google 23 a Amazon 18 M Microsoft 15

The key insight is that numbers divisible by 25 must end in 00, 25, 50, or 75. Best approach is greedy pattern matching - scan from right to find these patterns with minimum deletions. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Pattern Matching	O(n)	O(1)	Find the closest occurrence of patterns 00, 25, 50, 75 from right to left
Brute Force - Try All Combinations	O(2ⁿ)	O(n)	Generate all possible subsequences and check divisibility by 25

Greedy Pattern Matching — Algorithm Steps

Scan from right for second digit of pattern
Find first digit of pattern to the left
Calculate deletions needed
Try all patterns and return minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Targets

Numbers divisible by 25 end in 00, 25, 50, or 75

Right to Left Search

Find second digit first, then first digit

Calculate Deletions

Count digits to remove between pattern digits

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int solution(char* num) {
    int n = strlen(num);
    if (n == 1) {
        return (num[0] != '0') ? 1 : 0;
    }
    
    int minOps = n; // worst case: delete all to get 0
    
    // Check for patterns: 00, 25, 50, 75
    char patterns[][3] = {"00", "25", "50", "75"};
    
    for (int p = 0; p < 4; p++) {
        char secondDigit = patterns[p][1];
        char firstDigit = patterns[p][0];
        
        // Find rightmost occurrence of second digit
        int secondPos = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (num[i] == secondDigit) {
                secondPos = i;
                break;
            }
        }
        
        if (secondPos == -1) {
            continue;
        }
        
        // Find first digit to the left of second digit
        int firstPos = -1;
        for (int i = secondPos - 1; i >= 0; i--) {
            if (num[i] == firstDigit) {
                firstPos = i;
                break;
            }
        }
        
        if (firstPos == -1) {
            continue;
        }
        
        // Calculate deletions: everything except these two positions
        int deletions = n - 2;
        
        // Special case: if result would be "00", we need at least one more digit
        if (strcmp(patterns[p], "00") == 0 && firstPos == 0 && secondPos == 1 && n > 2) {
            int foundNonzero = 0;
            for (int i = 0; i < n; i++) {
                if (i != firstPos && i != secondPos && num[i] != '0') {
                    foundNonzero = 1;
                    break;
                }
            }
            if (foundNonzero) {
                deletions = n - 3; // keep one more non-zero digit
            }
        }
        
        if (deletions < minOps) {
            minOps = deletions;
        }
    }
    
    return minOps;
}

int main() {
    char num[100];
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    
    int result = solution(num);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string for each of 4 patterns

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Pattern Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler