Finding CB Numbers-Approach

#1

I am confused as to how to approach. for this question…please help as there are so many cases in this question

#2

Hey Saksham, here I am sharing one of the possible approaches :

According to the Problem the work is to find the Max CB numbers from the given number.

  • As to work on substrings of the given number, we will capture the element into the String instead of integer .
  • The number ‘n’ given is nothing to do with our approach(as we are working on String) but can be useful according to your approach.
    Intuition to solve this problem:
  • Put loop on string that will give substring of every length.
  • create a function that will return true if the passed number is a CB number otherwise return false.
  • To put a check if the digit is already a part of the any other CB number, create an boolean array say, valid which store which digits till now has been a part of any other CB number.
  • Take a counter and increment if a CB number is found.
  • At the end print the count.
#3

Thank you sir for help…i have successfully submitted it!

#4

#include<bits/stdc++.h>
using namespace std;
bool fact(int a)
{ if(a<=1)
return 0;
if(a<=3)
return 1;
if(a%3==0||a%2==0)
return 0;
for(int i=5;i*i<a;i=i+6)
if(a%(i)==0||a%(i+2)==0)
return 0;
return 1;

}
bool visited(int *v,int j,int i)
{
for(;i<=j;i++)
if(v[i]==1)
{
return 1;
}
return 0;
}
int main()
{
int n;
cin>>n;
string s;
cin>>s;
int count=0;
int v[n]={0};
for(int i=0;i<n;i++)
{
int num=0;

	for(int j=i;j<n;j++)
	{
		num=num*10+(s[j]-'0');
	
		if(fact(num)==1)
		{	
			if(!visited( v, j,i))
			{
				count++;
				for(int x=i;x<=j;x++)
					v[x]=1;
			}
		}
		
	}
}
cout<<count;

}
please help what is problem in my code as it fail 2 cases

#5

She is mam by the way . :grinning:.

#6

can someone please tell what’s wrong in my code, it fails 1 test case.
My code:-

#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll isprime(string s, int i,int j){
    string n;
    for(int a=i;a<=j;a++){
        n.push_back(s[a]);
    }
    ll number = stoull(n);
    // cout<<number<<endl;
    return number;
}
bool arr_ans(ll num){
    int arr[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };

        if(num==1){
            return false;
        }
        for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
            if (num == arr[i]) {
                return true;
            }
        }

        for (int i = 0; i < sizeof(arr)/sizeof(arr[0]); i++) {
            if (num % arr[i] == 0) {
                return false;
            }
        }
        return true;;
}
int main() {
    int n;
    cin>>n;
    bool used[n];
    for(int i=0;i<n;i++){
        used[i]=false;
    }
    string s;
    cin>>s;
    ll number = stoull(s);
    // int a[number+1];
    // for(ll i=0;i<=number;i++){
    //     a[i]=1;
    // }
    // a[0]=0;
    // a[1]=0;
    // a[2]=1;
    // a[3]=1;
    // for(ll i=4;i<=number;i=i+2){
    //     a[i]=0;
    // }
    // for(ll i=9;i<=number;i=i+6){
    //     a[i]=0;
    // }
    // for(ll i=5;i<=29;i=i+2){
    //     if(a[i]==1){
    //         for(int j=i*i;j<=number;j=j+(2*i)){
    //             a[j]=0;
    //         }
    //     }
    // }
    // cout<<a[8161]<<endl;
    // for(int i=0;i<=number;i++){
    //     cout<<i<<" "<<a[i]<<endl;
    // }
    
    ll temp=0;
    int count=0;
    int q=0;
    while(q<n){
        int i = 0;
        int j = i+q;
        int flag=0;
        for(int i=0;i<=j;i++){
            if(used[i]==true){
                flag=1;
            }
        }
        while(j<n && flag==0){
            int flag1=0;
            for(int u=i;u<=j;u++){
                if(used[u]==true){
                    flag1=1;
                }
            }
            if(flag1==0){
            temp = isprime(s,i,j);
            // cout<<temp<<endl;
            bool ans = arr_ans(temp);
            // cout<<"ans "<<ans<<endl;
            if(ans==true){
                // cout<<temp<<endl;
                count++;
                for(int k=i;k<=j;k++){
                    used[k]=true;
                }
                // for(int y=0;y<n;y++){
                //     cout<<used[y]<<" ";
                // }
                // cout<<endl;
            }
            }
            // if(a[temp]==1){
            //     cout<<temp<<endl;
            //     for(int k=i;k<=j;k++){
            //         used[k]=true;
            //     }
            //     i=j;
            //     count++;
            // }
            i++;
            j++;
        }
        q++;
    }
    cout<<count<<endl;
}