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.
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.
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Merge List
You are viewing a single comment's thread. Return to all comments →
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.