Wrong answer - CB Numbers

#1

I am getting 3 out of 9 test cases as failed.
Kindly have a look at the code.

#2

@mananaroramail,
Please share your code.

#3
#4

My approach is to make substrings of the given string and finding out the max possible cb numbers.
For instance :
if the number is 81615 then
first I will check for 8 (F) , 81(F) , 816(F) …
for 6 : 6( F ) , 61 ( T )
so update starting index to j
then 5 ( T )
Therefore answer is 2

#5

@mananaroramail,
What about checking if the digit is already a part of the any other CB number??
For this you can create an boolean array which stores which digits till now have been a part of any other CB number.

#6

That was great , But still one test case failed
I didn’t use array instead I converted the string before i and checked for each digit if it is CB or not

#7

@mananaroramail,
What about combination of digits?

#8

I used this algo to find out the max CB numbers for substring 0 to i as well but this also gave wrong answer, HOW ?
As this algo first goes for single digits and then goes for combination

#9

@mananaroramail,
can you share your code?

#10

import java.util.*;
public class Main {
public static void main(String args[]) {

	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();

	sc.nextLine();

	String str = sc.nextLine();

	int max = 0;
	
	for(int i = 0 ; i<n ; i++)
	{
		int count = 0;
		
		int si_t = 0;
		for(int j = 0 ; j<=i ; j++)
		{
			String temp = str.substring(si_t,j);
			if( CBNumber(temp) )
			{
				count++;
				si_t = j;
			}
		}

		int si = i;
		for(int j = i+1 ; j<=n ; j++)
		{
			String temp = str.substring(si,j);
			if( CBNumber(temp) )
			{
				count++;
				si = j;
			}
		}

		if( count > max)
			{
				max = count;
			}
	}

	System.out.println(max);
}

public static boolean CBNumber(String str)
{
	if( str.equals(""))
	{
		return false;
	}
	long num = Long.parseLong(str);

	if( num <= 1)
	{
		return false;
	}

	long [] arr = {2,3,5,7,11,13,17,19,23,29};

	for(int i = 0 ; i<arr.length ; i++)
	{
		if( num == arr[i])
		{
			return true;
		}
	}
	for(int i = 0 ; i<arr.length ; i++)
	{
		if( num % arr[i] == 0)
		{
			return false;
		}
	}

	return true;
}

}

#11

This is the part which I modified

#12

@mananaroramail,
Are you trying to find the length of the max CB number? Because if that’s the case then you are wrong. You need to find the max number of CB numbers in a given number such that they contain only each digit occurs once. Example: In 4991, both 499 and 991 are CB numbers but you can choose either 499 or 991, not both.
For the input:
4
4991
Your code gives 0, but the answer is 1.

Suggested approach:

  1. Put loop on string that will give substring of every length.
  2. Create a function that will return true if the passed number is a CB number otherwise return false.
  3. For checking if the digit is already a part of the any other CB number, create an boolean array which stores which digits till now has been a part of any other CB number.
  4. Take a counter and increment if a CB number is found.
  5. At the end print the count.

Sample input:
6
441441
Correct Answer: 2
Your answer: 1
Here 41,41 are the CB numbers, hence the answer will be 2.

#13

At last all test cases are passed.
I totally changed my approach. Instead of loops I used RECURSION.

#14

This testcase was very helpful , Thanks a lot