help September challenge chef and digit

https://www.codechef.com/SEPT17/problems/CHEFPDIG

the constraints are itself so dangerous , that I am not able to think of a way other then to store it as a string, but what to do next?

You can just loop from 65 to 65+26 and and check if a digit is present in the original array or not. Complexity would be O(26N) = O(N) . Solution here: https://www.codechef.com/viewsolution/15182329

1 Like

The questions seems easy enough though, but when you look at the constraint , you need to take the input as string , one more thing is there you need to print the characters alphabetically. So why not read the question from back , for instance if A can be made from the numbers then print A , if B can be made then print B , and so on till Z . Take an example of 778654891, then just make frequency array of 10 numbers initialized to 0 everywhere. So your freq array,looks something like this 0 1 0 0 1 1 1 2 2 1 so based on 0-based indexing you can simply store the frequency of each digits and refer to it by O(1). Now you need to check from A-Z whether its there or not so , just run a loop from 65-90. so for(65,90) and i=65 at first instance so a=I%10 and b=I/10 will give u a=5 and b=6 so you just need to check if its there or not freq[a]>0 and freq**>0 , if then print char(i) in c++ will print the character with ASCII value i. When you come down 66 , so 6 has to be present more then once so freq[a]>1 since you can use the same positions 6 twice as mentioned in the question, and you are done .

The solution is https://www.codechef.com/viewsolution/15183326.

The complexity is O(len(s)).

1 Like

thank you for such a detailed explanation . :slight_smile:

thank you but I cannot up vote unfortunately

No worries, all that matters is you learnt something. :slight_smile:

1 Like

Did you even try reading the editorial?