Problem in finding CB numbers

#1

May you suggest some approach or hint to solve this , as I am unable to think on it , all my approaches are failing at some point

#2

Hello @Divya_321,

In the question you have to find the maximum number of CB numbers that you can form from the input:
In the Sample Testcases:
Example 1:
5
81615
There are at max two CB numbers that we can form:
61
5
Thus, the output is 2.

Approach:

  1. check for all sub-strings of the given string of digits, starting from all strings of length 1 and then gradually checking for the strings of increasing size:

    1.1. check if the sub-string is CB number: for this, create a function
    1.1.1. if sub-string is 1 or 0 return false.
    1.1.2. if sub-string is any of the {2,3,5,7,11,13,17,19,23,29}, then return true.
    1.1.3. if sub-string is divisible by any of the {2,3,5,7,11,13,17,19,23,29}, then return false.
    1.1.4. return true

    1.2. now if it is a substring:
    1.2.1. call a function that marks the index as visited for indexes which are part of that CB number.

    1.3. increment the count for CB number.

2.Print the count

Hope, this would help.
If you still have any issue, feel free to ask.
Give a like if you are satisfied.

1 Like
#3

In step 1.1.4 it should be true because because for 61 ,it neither 1 or 2 , neither from cb set neither divisible from given cb set so it should return true know,.we are marking indexes of selected strings to ensure no more sub string can be generated from it an neither it becomes parent string of other strings???
Won’t I get tle for generating all substring,

#4

Hello @Divya_321,

  1. Yes, it should be true. I have corrected it.

  2. No, it won’t show TLE as the constraint on length is very small:
    1 <= Length of strings of digits <= 17

Hope, it is clear.

1 Like
#5

Thank you finally I got all test cases cleared

#6

@Divya_321 Please mark it as resolved.:slightly_smiling_face: