From a collection of $n$ items, the number of ways we can choose $k$ items, where the order among these $k$ items doesn’t matter, is expressed by $\displaystyle{n \choose k}$. This problems asks to find $\displaystyle{n \choose k}$ such that $n > 0$ and $0 \leq k \leq n$.

The bound for $n$ is not given. The only information given is that $\displaystyle{n \choose k}$ will always fit into an integer, i.e. it will be less than $2^{31}$.

The familiar formula for $\displaystyle{n \choose k}$ is [Source]:

\begin{eqnarray} \label{uva-530-eqn1} {n \choose k} = \ddfrac{n!}{k!(n - k)!} \end{eqnarray}

Let’s try to bound $n$. We ask the following question: what is the maximum value of $n$ such that $\displaystyle{n \choose k}$ is less than $2^{31}$?

To find the answer to the above question, we simplify \eqref{uva-530-eqn1},

\begin{eqnarray} \ddfrac{n!}{k!(n - k)!} & = & \ddfrac{n(n-1)(n-2)\ldots 1}{[k(k - 1)(k - 2) \ldots 1] (n-k)!} \nonumber \newline & = & \ddfrac{n(n-1)(n-2)\ldots (k + 1)}{(n-k)!} \nonumber \newline & = & \ddfrac{n(n-1)(n-2)\ldots (n - k + 1)\cancel{(n - k)}\cancel{\ldots}\cancel{(k + 1)}}{(\cancel{n-k)}\cancel{(n - k - 1)} \cancel{\ldots}\cancel{(k + 1)}k \ldots 1} \nonumber \newline \label{uva-530-eqn2} & = & \ddfrac{n(n -1)\ldots(n - k + 1)}{1.2.3 \ldots k} \end{eqnarray}

The denominator in \eqref{uva-530-eqn2} is devoid of $n$. Remember we are not interested in the value of $k$. We are trying to find the single biggest value of $n$ such that for any $k$, $\displaystyle{n \choose k} < 2^{31}$. So we put $k = 1$ in \eqref{uva-530-eqn2} to our convenience:

\[ \ddfrac{n(n -1)\ldots(n - 1 + 1)}{1.2\ldots 1} < 2^{31} \] \[ \implies \large n < 2^{31} \]

As $n$ is an integer, $n_{max} = 2^{31} - 1$. As $n_{max}$ is a very high number, we can’t just naively compute its factorial (and the result wouldn’t store in the primitive data types anyway). We have to use relation \eqref{uva-530-eqn2} to compute the value of $\displaystyle{n \choose k}$ as \eqref{uva-530-eqn2} is in reduced form.

Now that we’ve bounded $n$, we have to know two important pieces of information before we can start implementing our solution. The first one is that:

\begin{eqnarray} \label{uva-530-eqn3} {n \choose k} = {n \choose n - k} \
\end{eqnarray}

It is evident from \eqref{uva-530-eqn3} that the values of $\displaystyle{n \choose k}$ are symmetric. This can also be seen from Pascal’s Triangle. For example, for $k = 1$ and $k = n - 1$, the values of $\displaystyle{n \choose k}$ are same. The maximum value of $\displaystyle{n \choose k}$ occurs at $k = \floor{\ddfrac{n}{2}}$ or $k = \ceil{\ddfrac{n}{2}}$. The values of $\displaystyle{n \choose k}$ starts from $k = 0$ and it keeps on increasing strictly up to $k = \floor{\ddfrac{n}{2}}$. From $k = \ceil{\ddfrac{n}{2}}$ the values of $\displaystyle{n \choose k}$ starts decreasing and these values are the same ones we encountered on $k = \left[0, \floor{\ddfrac{n}{2}} \right]$ range (hence the symmetry). For more details, refer to this post.

So if we have $k > n - k$ or $k > \floor{\ddfrac{n}{2}}$, then we instead of iterating from $1$ to $k$ in the denominator of \eqref{uva-530-eqn2}, we can just iterate to $n - k$ as $k$ and $n - k$ ends up giving the same value for $\displaystyle{n \choose k}$. This way we can ensure that we have to iterate from $k = 1$ to at most $k = \floor{\ddfrac{n}{2}}$ in the worst case.

Another important piece of information is the following:

The product of $n$ consecutive integers is divisible by $n!$

Proof: Let the $n$ consecutive integers be $a + 1, a + 2, \ldots, a + n$. Now:

\begin{eqnarray} & \ddfrac{(a +1)(a + 2)\ldots(a + n)}{n!} \nonumber \
= & \ddfrac{a!~(a +1)(a + 2)\ldots(a + n)}{a!~n!} \nonumber \
= & \ddfrac{(a + n)!}{a!~n!} \nonumber \
= & {a + n \choose n} \nonumber \end{eqnarray}

As $\displaystyle{a + n \choose n}$ is an integer, the numerator is divided evenly by the denominator. $\blacksquare$

How is this information helpful to us? Look at identity \eqref{uva-530-eqn2} again. The numerator has numbers from $n - k + 1$ to $n$ (a total of $n - (n - k + 1) + 1 = k$ consecutive numbers). The denominator also has $k$ consecutive numbers. Because we have $n_{max} = 2^{31} - 1$ and $k_{max} = \floor{\ddfrac{n}{2}}$, the numerator can have $ 2^{31} - 1 - \left( 2^{31} - 1 - \floor{\ddfrac{2^{31} - 1}{2}} + 1 \right) + 1 = \floor{\ddfrac{2^{31} - 1}{2}}$ consecutive values starting from $\left( 2^{31} - 1 - \floor{\ddfrac{2^{31} - 1}{2}} + 1\right) = \ceil{\ddfrac{2^{31}-1}{2}} + 1 $ and ending at $2^{31} - 1$. The product of these consecutive integers will not fit into any primitive data type. So if we multiply all the numbers in the numerator of \eqref{uva-530-eqn2} and then try to divide the product by the denominator, then we’ll get a wrong answer.

If we take one number from the numerator, then it will be divided by $1!$. If we take two consecutive numbers from the numerator (for example, $n$ and $n - 1$), then their product will be divisible by $2!$. Now if we multiply $n(n-1)$ with $(n-2)$, then the result will be divisible by $3$. Why? Because $n(n-1)(n-2)$ is divisible by $3! = 3\times 2!$. As $n(n-1)$ has already been divided by $2!$, then $(n-2)$ must be divisible by $3$, otherwise the result would not be an integer and we know for a fact that the result is indeed an integer. Similarly, after dividing $n(n-1)(n-2)$ by 3, multiplying the result with $n - 3$, resulting in the product $\ddfrac{n(n-1)(n-2)(n-3)}{3}$, will be divisible by $4$ (in effect the product of these $4$ numbers are divisible by $4!$).

So our strategy will be to multiply and divide in each iteration. The division helps us to avoid overflow and because of the above theorem, we know that the division will result in an integer output.

Here’s the implementation in C++:

We can also solve this problem recursively. Let’s figure out the recurrence relation for $\displaystyle{n \choose k}$. When we have to choose $k$ items from a collection of $n$ items, we can either choose an item (then we have to choose $k - 1$ items from the remaining $n - 1$ items) or we can skip the item (then we have to choose the $k$ items from the remaining $n - 1$ items). The recurrence relation then boils down to:

\begin{eqnarray} \label{uva-530-eqn4} {n \choose k} = {n - 1 \choose k} + {n - 1 \choose k - 1} \end{eqnarray}

Replacing relation \eqref{uva-530-eqn1} in \eqref{uva-530-eqn4},

\begin{eqnarray} {n \choose k} & = & \ddfrac{(n - 1)!}{k! (n - k - 1)!} + \ddfrac{(n - 1)!}{(k - 1)!(n - k)!} \nonumber \newline & = & \ddfrac{(n - 1)!}{k(k - 1)! (n - k - 1)!} + \ddfrac{(n - 1)!}{(k - 1)!(n - k)(n - k - 1)!} \nonumber \newline & = & \ddfrac{(n - 1)!}{(k - 1)! (n - k - 1)!} \left[ \ddfrac{1}{k} + \ddfrac{1}{n - k} \right] \nonumber \newline & = & \ddfrac{(n - 1)!}{(k - 1)! (n - k - 1)!} \times \ddfrac{n}{k(n - k)} \nonumber \newline & = & \ddfrac{n}{k} \ddfrac{(n - 1)!}{(k - 1)! (n - k)!} \nonumber \newline \label{uva-530-eqn5} & = & \ddfrac{n}{k} \displaystyle{n - 1 \choose k - 1} \newline \end{eqnarray}

Here’s the recursive implementation in C++:

Time Complexity: As the loop or recursion runs $k$ times and $k_{max} = \floor{\ddfrac{n}{2}}$, the running time is $\mathcal{O}(n)$.