How to implement the nCr algorithm (combination) when n > 167 in JavaScript?

Question

I just got this challenge and I got stumped, blank. The question somewhat goes like this:

There are chess players that will play in duels. For example, 4 players (A, B, C, D), paired by 2, will yield a total of 6 chess games: AB, AC, AD, BC, BD, CD. Write a function taking an integer value and returning the number of possible combination.

Tests:
gameCount(4);     // 6
gameCount(10000); // 49995000

I remember, many years ago, my math class on linear problems, and this was one of them. A very quick Google search yielded the nCr formula. So I quickly wrote the code:

const r = 2;
const factorial = n => {
  let f = 1;
  for (let i = 2; i <= n; ++i) {
    f = f * i;
  }
  return f;
}
const gameCount = n => factorial(n) / (factorial(r) * factorial(n - r));

console.log( gameCount(4) );     // 6
console.log( gameCount(10000) ); // NaN

The NaN baffled me at first, but then I realized that 10000! is quite a large number!

How can I optimise gameCount to accept large numbers by still remaining linear?

Note: I am aware that the factorial function is not linear, but this was what I wrote at the time. The ideal solution would be to have everything linear, perhaps removing factorials altogether.

Keeping your code as it is, you can use BigInt (sharing a JSFiddle, posting this as an answer will only get downvotes: https://jsfiddle.net/pk850m1f/). Of course, since the result itself is not big (the problem is the intermediary step for doing that division), I believe you can find a better algorithm. — Gerardo Furtado, Feb 03 '23 at 01:48
Does this answer your question? [Calculate nCr in counting all possible paths problem](https://stackoverflow.com/questions/60696108/calculate-ncr-in-counting-all-possible-paths-problem) — Spektre, Feb 03 '23 at 07:30

Siguza · Accepted Answer · 2023-02-03T01:59:14.370

What you currently do is calculate two very big numbers that share a very big common divisor, and then divide one by the other. You could just not calculate that divisor (factorial(n - r)) in the first place.

Change your factorial function to take a minimum argument.

const r = 2;
const factorial = (n, m) => {
  let f = 1;
  for (let i = n; i > m; --i) {
    f = f * i;
  }
  return f;
}
const gameCount = n => factorial(n, n - r) / factorial(r, 0);

console.log( gameCount(4) );     // 6
console.log( gameCount(10000) ); // 49995000

Though note that this will only avoid the NaN issue as long as r is reasonably small. If you need it to work for cases where both n and r are big, you cannot use the native JavaScript number type. I suggest looking into BigInt for that case.

And for the sake of completeness, if the case r = 2 is all you care about, then your entire formula can be simplified to:

const gameCount = n => (n * (n - 1)) / 2;

I will have to scratch my head around that optimisation, but thank you! Ah!! The second solution is that one I had in mind, but couldn't figure, so I found the nCr on Google! — Yanick Rochon, Feb 03 '23 at 01:58
@YanickRochon I suggest you take a case like `n = 9` and write out the entire term on a piece of paper, after expanding the factorial. The common divisor should become quite apparent. — Siguza, Feb 03 '23 at 02:02

How to implement the nCr algorithm (combination) when n > 167 in JavaScript?

1 Answers1