Chef and Digits help

What is wrong in my approach,i just simply used hashing for every number l to r for 25 points,but got WA

My Code—>

import java.util.Arrays;

import java.util.Scanner;

class chefanddigitcount
{

``````public static void main(String[] args)
``````

{

`````` Scanner sc=new Scanner(System.in);

int t=sc.nextInt();
``````

while(t!=0)

{

``````    long l=sc.nextLong();
``````

long r=sc.nextLong();

int hash[]=new int[10];

for(int i=0;i<10;i++)
hash[i]=sc.nextInt();

`````` long ans=0;

for(long i=l;i<=r;i++)
{
String s="";
``````

s=Long.toString(i);

int countinword[]=new int[10];

long result1=0;
long result2=0;

for(int cnt=0;cnt<s.length();cnt++)
countinword[Integer.parseInt(Character.toString(s.charAt(cnt)))]++;

``````            for( int x=0;x<s.length();x++)
``````

{
result1=countinword[Integer.parseInt(Character.toString(s.charAt(x)))];

``````result2= hash[Integer.parseInt(Character.toString(s.charAt(x)))];

if( result1==result2 )
{

ans++;

break;

}
``````

}
}

``````     long rr=(r-l)+1;
``````

if (r==l && ans==0)//if l and r both are same,just for formality…lol

{

``````            System.out.println("0");
``````

}

``````        else
System.out.println(rr-ans);

t--;
``````

}

}}

The problem is that you’re counting the number of occurrences of each digit in every integer from l to r, and then checking whether the count of any digit in that number is equal to the required count of that digit. What you’re forgetting is that it’s possible that for some digit i, a[i] = 0. And if that digit is missing in our current number, then we need to discard it, since countinword[i] = hash[i] = 0 for that digit i. But you don’t check that i, since it doesn’t occur in our number.

You should change these lines in your code:

``````for(int x=0; x!=s.length(); x++) {
result1=countinword[Integer.parseInt(Character.toString(s.charAt(x)))];
result2= hash[Integer.parseInt(Character.toString(s.charAt(x)))];
if(result1 == result2) {
ans++;
break;
}
}
``````

Here instead of iterating over each digit in the number, you should iterate over all possible digits [0-9] and check whether countinword[i] == hash[i].

2 Likes

Lol, m at phone else i would have corrected the formatting. Btw, is this doubt after checking editorial?

@vijju123, you don’t need to comment/answer on every question. No one is interested whether you are using phone or laptop. Simply, answer the question, if you know!

1 Like

yes…why i am gettin wa with same approach for 25 points?

@pratik_gadhiya - Now haters have problem with me commenting. Lol. Btw in case you failed to notice, my promary intution was to know if he checked the editorial. You have problem with me commenting, report to @admin (and u know whose wrong if no action os taken ;-). )

got it…but check my this solution where i also check if result1!=0 && result2!=0, but Wa…link for solution-https://www.codechef.com/viewsolution/13342641

@vivek96 Why are you using the condition “(countinword[i] != 0 && hash[i] != 0)”? If both are zero, that means that the condition is satisfied, and Chef dislikes this number, so we need to remove it. Your same solution with this condition removed gets AC: https://www.codechef.com/submit/complete/13351818

because im counting the dislike ones,and then used long rr=(r-l)+1; sout(rr-ans)…

means if hash[i]==0 for some i and this character is also not present in string (means present zero times) then also we have to increase count of dislike?

Yes! Problem statement says “If for an integer x, suppose there exists some digit i (0 ≤ i ≤ 9) which appears exactly ai times in the decimal presentation of x (without leading zeros), then Chef dislikes x.” So if ai = 0 for some digit i, and this digit appears 0 times in a number, then Chef dislikes it. Hope this helps

for proper clarification,please provide that test case.

and what is role of without leading zeros (line) in question

Test case:

1

15 17

9 9 9 9 9 9 9 9 0

Answer should be 0, since 15, 16 and 17 all have 0 number of digit 9.

Leading zeroes line just means that when counting occurrences of the digit 0, don’t count any leading ones (So 001204 has 1 zero).

okay,Thanks a lot…Happy Coding!