All challenges
Easy 0 solved 0% acceptance

Binomial Coefficient

Count the ways to choose k items out of n (n choose k).

What you'll learn

  • Compute combinations without factorials
  • Apply Pascal's rule
  • Handle k greater than n

Problem

The binomial coefficient C(n, k), read "n choose k", is the number of ways to pick k items from n different items when order does not matter. The formula n! / (k! (n − k)!) overflows quickly if you compute the factorials first, so build the answer step by step or use Pascal's rule C(n, k) = C(n − 1, k − 1) + C(n − 1, k).

Implement binomial_coefficient(n, k).

Input

n: The number of items.

k: How many to choose.

Output

Return C(n, k). If k > n there is no way to choose, so return 0.

Constraints

0 ≤ n ≤ 66

0 ≤ k ≤ 100

Examples

Example 1
Input:
n = 5
k = 2

Expected output:
expected = 10
Input:
long long n = 5;
long long k = 2;

Expected output:
long long expected = 10;
Input:
long n = 5;
long k = 2;

Expected output:
long expected = 10;

Explanation

The pairs from 5 items number 5 × 4 / 2 = 10.

Example 2
Input:
n = 6
k = 0

Expected output:
expected = 1
Input:
long long n = 6;
long long k = 0;

Expected output:
long long expected = 1;
Input:
long n = 6;
long k = 0;

Expected output:
long expected = 1;

Explanation

There is exactly one way to choose nothing: 1.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

Factorials of numbers above 20 do not fit in 64 bits, so avoid them.

Hint 2

One row of Pascal's triangle can be updated in place from right to left.

Hint 3

C(n, k) equals C(n, n − k), and it is 0 when k > n.

Expected complexity

O(n · k) time, O(k) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.