Codeforcess Solution 1593-B B. Make it Divisible by 25 ,C++, Java, Js and Python

Algorithm

It is given a positive integer $n$ . In $1$ move, one can select any single digit and remove it (i.e. one selects some position in the number and removes the digit located at this position). The operation cannot be performed if only one digit remains. If the resulting number contains leading zeroes, they are automatically removed.

E.g. if one removes from the number $32925$ the $3$ -rd digit, the resulting number will be $3225$ . If one removes from the number $20099050$ the first digit, the resulting number will be $99050$ (the $2$ zeroes going next to the first digit are automatically removed).

What is the minimum number of steps to get a number such that it is divisible by $25$ and positive? It is guaranteed that, for each $n$ occurring in the input, the answer exists. It is guaranteed that the number $n$ has no leading zeros.

Input

The first line contains one integer $t$ ( $1 \leq t \leq 10^{4}$ ) — the number of test cases. Then $t$ test cases follow.

Each test case consists of one line containing one integer $n$ ( $25 \leq n \leq 10^{18}$ ). It is guaranteed that, for each $n$ occurring in the input, the answer exists. It is guaranteed that the number $n$ has no leading zeros.

Output

For each test case output on a separate line an integer $k$ ( $k \geq 0$ ) — the minimum number of steps to get a number such that it is divisible by $25$ and positive.

Example
input
Copy
5
100
71345
3259
50555
2050047
output
Copy
0
3
1
3
2

Note

In the first test case, it is already given a number divisible by $25$ .

In the second test case, we can remove the digits $1$ , $3$ , and $4$ to get the number $75$ .

In the third test case, it's enough to remove the last digit to get the number $325$ .

In the fourth test case, we can remove the three last digits to get the number $50$ .

In the fifth test case, it's enough to remove the digits $4$ and $7$ .

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int totcount(string s, string t) {
    int count = 0;
    int l = s.length();
    while(s.length() > 0 && t.length() > 0) {
        if(s.back() == t.back()) {
            t.pop_back();
        }
        else {
            count++;
        }
        s.pop_back();
    }
    if(t.length() == 0){
      return count;
    }
    return l;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--) {
        string s;
        cin>>s;
        if(s.length() < 2) {
            cout << s.length()<<endl;
        } else {
            cout<<min({totcount(s,"00"),totcount(s,"25"),totcount(s,"50"),totcount(s,"75")})<<endl;
        }
    }
  }

Copy The Code & Try With Live Editor

Input

–

cmd

5
100
71345
3259
50555
2050047

Output

–

cmd

0
3
1
3
2

Demonstration

Codeforcess Solution 1593-B B. Make it Divisible by 25 ,C++, Java, Js and Python ,1593-B,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution

Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+

Try With Live Editor

Category - Codeforces Online Judge Maniruzzaman Akash 1 year ago 482 0