PROBLEM LINK:
Author: Arush Nagpal
Tester: Rahul Johari
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Maths, Greedy, Sorting
PROBLEM:
Defined a function F(x) for positive integer x as the product of factorials of its constituting digits.
Given a number N that contains d digits and contains at least one digit larger than 1.
The problem is to find maximum positive number M which should contain neither the digit 0 nor the digit 1 and also F(M) = F(N).
The number N may possibly start with leading zeroes.
EXPLANATION:
Conclusion first:
First, we transform each digit of the original number as follows:
0, 1 -> empty
2 -> 2
3 -> 3
4 -> 322
5 -> 5
6 -> 53
7 -> 7
8 -> 7222
9 -> 7332
Then, sort all digits in decreasing order as a new number, then it will be the answer.
We can observe that our answer won’t contain digits 4,6,8,9, because we can always transform digits 4,6,8,9 to more digits as in the conclusion, and it makes the number larger.
Then, how can we make sure that the result is the largest after this transformation?
For any positive integer x, if it can be written as the form (2!)c2 * (3!)c3 * (5!)c5 * (7!)c7, there will be only one unique way.
Suppose that there exists two ways to write down x in this form, we can assume that the two ways are (2!)a2 * (3!)a3 * (5!)a5 * (7!)a7 and (2!)b2 * (3!)b3 * (5!)b5 * (7!)b7.
We find the largest i such that ai???bi, Then we know there exists at least one prime number whose factor is different in the two ways.
But according to the Fundamental Theorem of Arithmetic, there is only one prime factorization of each integer. So we get a contradiction.
After getting the result, we don’t need to worry about other numbers being larger than ours.
Time Complexity: O(n).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.