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 makenumspecial.
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.
Intuition
Approach 1:
DP
Take/ Not Take
Not able to solve in the contest, Because passing string as parameter, Rather
Than passing number
And taking minimum
Approach 2:
Number divisible by 25, when last two nums are 00,25,50,75
Then take two pointers and iterate
Take care of one 0 condition, in that case we delete all
Links
Video Links
Approach 1:
DP
C++
class Solution {
public:
vector<vector<int>> dp;
int find_ans(string &s, int index, int temp){
if(index == s.size()){
if(temp % 25 == 0) return 0;
return 1e9+7;
}
if(dp[index][temp] != -1)
return dp[index][temp];
int not_del = 1 + find_ans(s, index+1, temp);
int digit=s[index]-'0';
int del = find_ans(s, index+1, (temp*10+digit)%25);
return dp[index][temp] = min(del, not_del);
}
int minimumOperations(string num) {
dp = vector<vector<int>> (102, vector<int>(27,-1));
return find_ans(num, 0, 0);
}
};
Approach 2:
Looping
C++
class Solution {
public:
int minimumOperations(string num) {
int n=num.size();
int ans=num.size();
// Worst case all deletion
for(int i=n-1; i>=0; i--){
for(int j=i-1; j>=0; j--){
int temp = (num[j]-'0')*10 + (num[i]-'0');
if(temp %25 == 0)
ans = min(ans, n-j-2);
}
if(num[i] == '0')
ans = min(ans, n-1);
}
return ans;
}
};