Finding CB Numbers

#1

Deepak and Gautam are having a discussion on a new type of number that they call Coding Blocks Number or CB Number. They use following criteria to define a CB Number.

0 and 1 are not a CB number.
2,3,5,7,11,13,17,19,23,29 are CB numbers.
Any number not divisible by the numbers in point 2( Given above) are also CB numbers.
Deepak said he loved CB numbers.Hearing it, Gautam throws a challenge to him.

Gautam will give Deepak a string of digits. Deepak’s task is to find the number of CB numbers in the string.

CB number once detected should not be sub-string or super-string of any other CB number.
Ex- In 4991, both 499 and 991 are CB numbers but you can choose either 499 or 991, not both.

Further, the CB number formed can only be a sub-string of the string.
Ex - In 481, you can not take 41 as CB number because 41 is not a sub-string of 481.

As there can be multiple solutions, Gautam asks Deepak to find the maximum number of CB numbers that can be formed from the given string.

Deepak has to take class of Launchpad students. Help him by solving Gautam’s challenge.

PLEASE CHECK MY CODE AND CORRECT IT ALSO COMMENT THE CHANGES YOU HAVE MADE IN IT

#2

Hey @dhruvk3k discuss your approach as i can see it’s not ideal for solving this problem. I can explain you mine approach but first i want you to understand why your approach is not ideal and after that i will explain you mine

#3

please tell me why my approach is wrong

#4

Your code will fail these test cases as what we actually have to do in this question is:

  • 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.

I am showing you this for one iteration and you can do it for rest

image
image1812×1049 269 KB

As you can see we will get numbers like 23,3,35,357,3572
We have to check for these numbers are they cb number or not, and if they are we also have to check if the digit is already a part of the any other CB number or not
Also attaching code for same algorithm so that you can get a crystal idea for this problem

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

#include
#include
#include
using namespace std;

vector cb = {2,3,5,7,11,13,17,19,23,29};

bool is_cb(int n){
if(n==1 || n==0){
return false;
}
for(int i = 0 ; i<cb.size() ; i++){
if(n%cb[i]==0 and n!=cb[i]){
return false;
}
}
return true;
}

int main(){
int n;
cin>>n;
string l;
cin>>l;
int count = 0;
for(int i = 0 ; i<n ; i++){
int a = 0;
for(int j = i ; j<n ; j++){
a = a*10 + (l[j]-‘0’);
// cout<<a<<endl;
if(is_cb(a)){

             count++;
			 i = j;
			 break;
		  }
	}
}

cout<<count<<endl;
return 0;

}
this is my code but 3 test case is failing plz hellp