PROBLEM LINK:
Author: sahilarora.535
DIFFICULTY:
SIMPLE
PREREQUISITES:
None
PROBLEM:
Given a number N, output (N!)%1589540031
EXPLANATION:
Memoize all the factorials till 10^5 before the test cases and store them in an array Fact. Then directly print Fact(N).
Program Complexity = O(T*1), i.e. O(T), where T is the number of test case.
ALTERNATIVE SOLUTION:
There was this alternate solution which could be deciphered by looking at the number mod, which was equal to 1589540031 = (3^13)*997. So basically, even by naive approach, one needed to find the modulo only upto 996!, because after that, the factorial would be completely divisible by the mod, and hence the answer would be 0.
Program Complexity = O(T*997), which would pass in 1 second.
AUTHOR’S SOLUTIONS:
Solution 1(by method 1 - memoization) - here.
Solution 2(by alternative method) - here
