Finding Cb number - help

#1

I tried implementing the editorial code in C++. I am passing 3 test-cases out of 9. Can you please tell what’s going wrong in the code?
https://ide.codingblocks.com/s/70612

#2

Hi Amartya, in your implementation, the substrings are generating a bit different. And that is causing the problem. Since we have to output the maximum no. of CB numbers that can be formed, the numbers shall be generated and checked in a specific manner. Consider a testcase 81615. While nos. should be generated in a pattern like this:

8
81
816
8161
81615
1
16
161
…
…
…
5

The nos. are generated in a pattern like this:

8
16
615
15
5
…

You can see them by adding a line:

cout <<"Num gen is: " << x << endl ;
// after line covert >> x ; in main function b/w line 58 & 59

Rectify this error by generating substring using some other method.

Hope this helps :slight_smile:

#4

Sir, I tried correcting the error, but it did not help much, test case 5 passed but not the others. Can you please see to it and tell me the needed correction?

#5

Hi Amartya, there is a problem with the boundaries of loops:

  1. in main (near line 65) when you assign visited[i] = true
          It should be just < instead of <=
  2. in isValid when you check if visited[i] == true or not.
          It should be <= instead of just <

Also, in the loop in 1. you have used i again in the nested loop. i.e. u have did this :

for( int i = … ) {
      …
      for ( int i = … ) {
      …
      }
      …
}

so change the iterator name in nested loop also. this mistake is at one more place.

Do these changes and then your code will run perfectly fine :slight_smile:

#6

The testcases didn’t passed because the above corrections were required. And the logic which I stated, the pattern of generation of numbers is correct and required.

#7

sir i have made the corrections which you pointed out , but didnt help.

#8

Hi Amartya, in your code when last numbers are generated at the value of i and o are not proper. Check it by adding line :

cout<<"num gen "<<x << ’ ’ << o << ’ ’ << i << " of len " << o-i <<endl;

at line 60. I again recommend you to generate substring by other method instead of using stringstream…