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

Time:02-03

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.

CodePudding user response:

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;
  • Related