Finding the cb numbers

i didn’t got the logic

1 Like

hey @ynikhil1999, here is the logic
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.

2 Likes

sir,i have seen the editorial but i didn’t understood the code
so plzz send the code along with comments in simplified manner

hey @ynikhil1999, based on above approach only. https://ide.codingblocks.com/s/91132

i didn’t got the question properly…

could u tell that for input 44166181111
how and what will be the output

hey @ynikhil1999, these are outputs for this testcase
41
61
11
11

All fulfilling criteria of CB numbers

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.

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


bool isCBNumber(long long num)
{
	if(num==0 || num==1)
		return false;
	int ref[10] = {2,3,5,7,11,13,17,19,23,29};
	for(int i=0; i<10; i++)
	{
		if(num-ref[i] == 0)
			return true;
	}
	for(int i=0; i<10; i++)
	{
		if(num%ref[i] == 0)
			return false;
	}
	return true;
}

bool isvalid(bitset <17> &visited, int start, int end)
{
	for(int i=start; i<end; i++)
	{
		if(visited[i])
			return false;
	}
	return true;
}





void util(string s, int len)
{
	bitset<17> visited;
	int count = 0;
	for(int l =1; l <= len; l++) // len loop gives the length of substring
	{
		for(int start = 0; start <= len - l; start++)
		{
			int end = start + l;
			string sub = s.substr(start, l);
			// cout << sub << endl;
			// cout << visited << endl;
			if(isCBNumber(stoll(sub)) && isvalid(visited, start, end))
			{
				count++;
				// cout << visited << endl;
				for(int i=start; i<end; i++)
					visited[i] = 1;
			}
		}
	}
	cout << count << endl;
}



int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif	
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

	int len; cin >> len;
	string s; cin >> s;
	util(s, len);
	return 0;
}
1 Like

i am unable to understand few part of the code…how are you checking if two numbers are substring or not?

i think this output is not follow this line
In 481 , you can not take 41 as CB number because 41 is not a sub-string of 481

I guess 181 will also be the output for same?