Hackerrank Solution: Sherlock and Permutations

Original Problem

Watson asks Sherlock: Given a string S of N 0's and M 1's, how many unique permutations of this string start with 1?

Help Sherlock by printing the answer modulo \((10^9+7)\).

Input Format

First line contains T, the number of test cases. Each test case consists of N and M separated by a space.

Output Format

For each test case, print the answer modulo \((10^9+7)\).

Constraints

• \(1 \leq T \leq 200\)
• \(1 \leq N,M \leq 1000\)

Solution

In total we have \(M+N\) bits in the string. Since the first bit has to be 1, we have \(M+N-1\) places, from which we choose exactly \(N\) zeros under the modular concurrence. So the solution to our problmem is

\[{M+N-1\choose N}\equiv \frac{(M+N-1)!}{N!(M-1)!} \pmod{10^9+7}\]

For Project Euler Problem 16 we implemented a highly optimized n over k algorithm with complexity \(O(k)\):

def noverk(n, k):
    c = 1
    k = min([k, n - k])
    n = n - k
    for i in range(1, k + 1)
        c = c * (n + i) / i
    return c

Converting this algorithm to an algorithm which operates under a modular concurrence should be easy, as the recursive nature of the algorithm can make use of the modular multiplication property

\[(a\cdot b)\bmod m = (a\bmod m \cdot b\bmod m)\bmod m\]

The only problem is the factor \(\frac{1}{i}\), which requires taking the modular inverse of \(i\). But since \(10^9+7\) is prime, we can make use of Eulers Theorem, which will make things much easier!

In general, Eulers Theorem states that if $\gcd(a, n) = 1$, then

\[a^{\varphi(n)} \equiv 1\pmod{n}\]

But since \(n\) is a prime number \(p=10^9+7\) in our case, we get

\[a^{p-1} \equiv 1\pmod{p}\]

Dividing both sides by \(a\) gives us a solution for the modular inverse under a prime number \(p\):

\[a^{p-2} \equiv a^{-1}\pmod{p}\]

When implementing the solution in Python, we can use the pow() function with its third argument for modular exponentiation to save an own implementation. All in all, the solution then looks like this

def noverkmodm(n, k, m):
    c = 1
    k = min([k, n - k])
    n = n - k;
    for i in range(1, k + 1):
        c = (c * ((n + i) % m) * pow(i, m - 2, m)) % m;
    return c

def solve(n, m):
    return noverkmodm(n + m - 1, n, 10 ** 9 + 7)