PINBS - Editorial

editorial
, ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Arun Sharma
Tester: Venkata Nikhil Medam, Tejas Pandey
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Given a binary string S, check if there exists a substring whose decimal representation is a prime number.

QUICK EXPLANATION:

The answer is \texttt{Yes} only if a substring 10 or 11 exists in the string S.

EXPLANATION:

Subtask 1: length(S) \leq 10

A possible solution is to generate all possible substrings. For each substring, convert it into decimal form, and check if it is prime using primality test.
If N is the length of the string, then, the worst case complexity for implementing this would be O(N^2 \cdot N \cdot N) i.e. O(N^4) which is sufficient for passing this subtask.

Subtask 2: length(S) \leq 10^4

  • For length 1, the possible strings are 0 and 1 with decimal values 0 and 1 respectively. The answer for both these values is \texttt{No}.

  • For length 2, the possible strings are 00, 01, 10, 11. The respective decimal values for these strings are 0, 1, 2 and 3. Out of these, 2 and 3 are prime numbers. Thus, the answer is \texttt{Yes} for strings 10 and 11.

  • For strings of length > 2, the answer is \texttt{Yes} only if a substring 10 or 11 exists in the string.

Claim: If the string has a substring 10 or 11, the answer is \texttt{Yes}.
Proof: The decimal value of 10 is 2 and that of 11 is 3. Both of these are prime numbers and thus, the answer is \texttt{Yes}.

Claim: If the string does not contain any substring equal to 10 or 11, the answer is \texttt{No}.
Proof: Given that there is no substring equal to 10 or 11, the string can only look like one of the following-

  1. 00…000 : In this case, for any substring, the decimal representation is 0. Thus the answer is \texttt{No}.
  2. 00…001 : In this case, for any substring, the decimal representation is either 0 or 1. None of these values is prime, and thus the answer for this case is also \texttt{No}.

Conclusion: The answer is \texttt{Yes} only if a substring 10 or 11 exists in the string S, otherwise it is \texttt{No}. An elegant way to check this is to check the values of all the characters of the string other than the last character. If any of the characters (other than the last character) is 1, the answer will be \texttt{Yes}.

TIME COMPLEXITY:

The time complexity is O(length(S)) per test case.

SOLUTION:

Setter's Solution 
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

// using namespace __gnu_pbds;

#define ll long long int

#define ld long double
#define forn(i, x, n) for (ll i = x; i < n; i++)
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define MOD 1000000007
#define MAX 200001
const int64_t INF = 1e17;
// #define endl "\n" //REMOVE in interaction problem

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll t;
    cin >> t;
    while (t--)
    {
        /* code */

        string s;
        cin >> s;

        ll n = s.size();
        ll fl = 0;
        if (n == 1)
            cout << "No\n";
        else
        {
            for (int i = 1; i < n; i++)
            {

                if (s[i] == '1' && s[i - 1] == '1')
                    fl = 1;

                if (s[i] == '0' && s[i - 1] == '1')
                    fl = 1;
            }

            if (fl == 1)
                cout << "Yes\n";
            else
                cout << "No\n";
        }
    }
}
Tester's Solution 
#include <iostream>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        string s;
        cin >> s;
        int found = 0;
        for(int i = 0; i < s.size() - 1; i++)
            found |= (s[i] - '0');
        cout << (found?"YES\n":"NO\n");
    }
}
Editorialist's Solution 
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n;

void solve()
{
    string s;
    cin>>s;
    
    n = s.length();
    bool found  = false;

    for(int i = 0; i<n-1; i++){
        if(s[i]=='1'){
            found = true;
            break;
        }
    }

    if(found){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}
3 Likes