We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Mathematics
- Combinatorics
- Merge List
- Discussions
Merge List
Merge List
Sort by
recency
|
19 Discussions
|
Please Login in order to post a comment
This passes all the test cases:
Hi java coder: https://github.com/AmitRoy3370/HackerRank/blob/master/Merge%20List
BigInteger all the way
from math import factorial as f
for _ in range(int(input())):
I'd like to give more intuition to neverloseks statement that the answer is (m+n)!/n!m!
The first thing to notice is that without order restrictions, we have n+m positions and n+m items... we're talking about permutations, so (n+m)P(n+m) or (n+m)/[(n+m)-(n+m)]! or just (n+m)!.
However, the restrictions on order means that n2 is restricted by n1, n3 by n1 and n2 and so on, and the same for m. Meaning that for each value nx, exactly x values are restricted. Therefore (n+m)! must be divided by n! and m!
I also just solved this using multiplicative inverse under modulo (in Python, so I just used
pow
instead of implementing the squaring algorithm), where x^-1 = x^(M-2)%M where M is the modulus rather than trying to divide.