PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
EXPLANATION:
The naive but wrong approach is to count the digits and print them in increasing order for smallest number (Let’s call it S) and in decreasing order for largest number (Let’s call it L). Although this gives the correct L, the smallest number is a bit tricky and this approach gives the wrong result.
The thing to notice is that both S and L should have the same number of occurrences of digits and should be valid i.e., no leading zeros.
For example, if the input was:
1 3 50 24 93
The actual output is:
203459 954320
But the output of naive approach will be:
023459 954320
This is wrong because 023459 is not valid. It is just 23459, which does not have the same number of occurrences of digits.
Now, we can start solving the problem.
The constraints say N is less than 1018 , hence long long int should suffice.
We first count the number of occurrences of digits and store it in an array (Let’s call it count) such that count[i] has the the number of times i has occurred. This is a good way of counting number of occurrences. For digits, the size of count can be 10, to store counts of digits 0 to 9. For alphabets, the size of count can be 26, for each alphabet.
A simple snippet that does this:
read n
while n is not zero:
count[n%10] = count[n%10] + 1
n = n / 10
This problem can be easily extended to N > 1018. In that case, it is better to read N as a string. Counting can be done as,
read n
for each character c in n
count[c-'0'] = count[c-'0'] + 1
For finding S, traverse count to find the smallest non-zero number i that has occurred at least once. Print that number once, followed by the number of times 0 occurs, and continue printing the rest of the numbers in increasing order.
For finding L, traverse count and print the numbers in decreasing order.