PROBLEM LINK:
Author: Shikhar Kunal
Editorialist: Shikhar Kunal
DIFFICULTY:
EASY.
PREREQUISITES:
Math, Factorial
PROBLEM:
Given two strings representing repeated factorials of two input numbers. Compare them.
EXPLANATION:
It is not always possible to calculate the value by applying the factorial operation as the value will be very large. But the logic for this problem can be inferred from the constraints given in the problem. The integer part will always contain a value less than 10^9. The first number to have its factorial in the order of 10^9 is 12. So for all numbers less than or equal to 12, we expand one factorial sign and replace the no with the expanded number. We keep on doing this until the expanded number can overshoot 10^9. So, we keep on expanding only the numbers less than or equal to 12. We can choose to expand upto any number say 15, provided its factorial can be stored in a data type.
Example –
3!!!
4!!
3!!! Is expanded to 6!! because 3 is less than or equal to 12. Again 6!! Is expanded to 24!. Now 24! Is not expanded because it will exceed 10^9. So our first number is 24!
4!! Is expanded to 24!.
After the final expansion of the numbers, we will compare first the number of remaining factorial signs. If they are same, we will compare the integer part after the expansion to get the output.
This is because we are guaranteed that integer part of any input number will not exceed 10^9 and integer part of our expanded number will exceed 10^9 if we expand it one more time (is possible). Therefore, just by comparing the number of remaining factorial signs we can get the answer.
AUTHOR’S SOLUTIONS:
Author’s solution can be found here.